备战秋招60天算法挑战,Day15
题目链接: https://leetcode.cn/problems/minimum-window-substring/
视频题解: https://www.bilibili.com/video/BV1sJ4m1g727/
LeetCode 76. 最小覆盖子串
题目描述
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
- 对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。 - 如果
s
中存在这样的子串,我们保证它是唯一的答案。
举个例子:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
视频题解
最小覆盖子串
思路来源
思路来源
思路解析
本题是经典的滑动窗口类型,解决这类问题的关键是窗口左右边界的滑动策略。
定义hash
表u_mapT
保存字符串t
中字符的频率,hash
表u_mapWindow
保存滑动窗口中字符出现的次数,left
保存窗口的左边界,right
保存窗口的右边界,resStart
保存最小候选窗口的起点,resLen
保存最小候选窗口长度。
窗口滑动策略如下:
u_mapT
中的元素不全在u_mapWindow
中,right
向右滑动,并更新u_mapWindow[s[right]]++
,直到u_mapT
中的元素全在u_mapWindow
中。u_mapT
中的元素全在u_mapWindow
中,left
向右滑,并更新u_mapWindow[s[left]]--
、最小候选窗口的起点resStart
和最小候选窗口长度resLen
,直到u_mapT
中的元素不全在u_mapWindow
中。
根据上面的策略我们可以获得以s
任意位置为左边界(枚举左边界)的所有候选窗口,只需要把其中最短的一个窗口返回即可。
这里在判断u_mapT
中的元素是否完全在u_mapWindow
中并没有采用遍历u_mapT
对其中的元素一个个去u_mapWindow
中比较。而是借用了一个整型变量tInWindow
在窗口滑动的过程中就对窗口中字符情况进行统计,大大节省了每次判断都要去遍历hash
表的时间。
C++代码
class Solution {
public:string minWindow(string s, string t) {int s_len = s.length();int t_len = t.length();if (s_len == 0 || t_len == 0) {return "";}//保存t中字符出现的次数unordered_map<char, int> u_mapT;//保存window中的字符出现的次数unordered_map<char, int> u_mapWindow;//统计t中的字符for (int i = 0; i < t_len; ++i) {u_mapT[t[i]]++;}//t中不重复字符的个数int tCount = u_mapT.size();//window完全包含t中不重复字符的数量int tInWindow = 0;int resStart = 0, resLen = INT_MAX;int left = 0, right = 0;while (right < s_len) {u_mapWindow[s[right]]++;//假设字符a在t和window中出现的次数相等,就增加tInWindow的计数if (u_mapT.count(s[right]) && u_mapWindow[s[right]] == u_mapT[s[right]]) {++tInWindow;} while (tInWindow == tCount) {//窗口的大小小于已保存的最小长度,更新最小长度if (right - left + 1 < resLen) {resStart = left;resLen = right - left + 1; }//右移窗口左边界,缩小窗口 u_mapWindow[s[left]]--;if (u_mapT.count(s[left]) && u_mapT[s[left]] > u_mapWindow[s[left]]) {--tInWindow;}++left;}++right;} if (resLen == INT_MAX) return "";return s.substr(resStart, resLen);}
};
java代码
class Solution {public String minWindow(String s, String t) {int s_len = s.length();int t_len = t.length();if (s_len == 0 || t_len == 0) {return "";}//保存t中字符出现的次数Map<Character, Integer> u_mapT = new HashMap<>();//保存window中的字符出现的次数Map<Character, Integer> u_mapWindow = new HashMap<>();//统计t中的字符for (int i = 0; i < t_len; ++i) {u_mapT.put(t.charAt(i), u_mapT.getOrDefault(t.charAt(i), 0) + 1);}//t中不重复字符的个数int tCount = u_mapT.size();//window完全包含t中不重复字符的数量int tInWindow = 0;int resStart = 0, resLen = Integer.MAX_VALUE;int left = 0, right = 0;while (right < s_len) {u_mapWindow.put(s.charAt(right), u_mapWindow.getOrDefault(s.charAt(right), 0) + 1);//假设字符a在t和window中出现的次数相等,就增加tInWindow的计数if (u_mapT.containsKey(s.charAt(right)) && u_mapWindow.get(s.charAt(right)).equals(u_mapT.get(s.charAt(right)))) {++tInWindow;}while (tInWindow == tCount) {//窗口的大小小于已保存的最小长度,更新最小长度if (right - left + 1 < resLen) {resStart = left;resLen = right - left + 1;}//右移窗口左边界,缩小窗口u_mapWindow.put(s.charAt(left), u_mapWindow.get(s.charAt(left)) - 1);if (u_mapT.containsKey(s.charAt(left)) && u_mapWindow.get(s.charAt(left)) < u_mapT.get(s.charAt(left))) {--tInWindow;}++left;}++right;}if (resLen == Integer.MAX_VALUE) return "";return s.substring(resStart, resStart + resLen);}
}
python代码
class Solution:def minWindow(self, s: str, t: str) -> str:s_len = len(s)t_len = len(t)if s_len == 0 or t_len == 0:return ""#保存t中字符出现的次数u_mapT = defaultdict(int)#保存window中的字符出现的次数u_mapWindow = defaultdict(int)#统计t中的字符for char in t:u_mapT[char] += 1#t中不重复字符的个数tCount = len(u_mapT)#window完全包含t中不重复字符的数量tInWindow = 0resStart, resLen = 0, float('inf')left, right = 0, 0while right < s_len:u_mapWindow[s[right]] += 1#假设字符a在t和window中出现的次数相等,就增加tInWindow的计数if s[right] in u_mapT and u_mapWindow[s[right]] == u_mapT[s[right]]:tInWindow += 1while tInWindow == tCount:#窗口的大小小于已保存的最小长度,更新最小长度if right - left + 1 < resLen:resStart = leftresLen = right - left + 1#右移窗口左边界,缩小窗口u_mapWindow[s[left]] -= 1if s[left] in u_mapT and u_mapWindow[s[left]] < u_mapT[s[left]]:tInWindow -= 1left += 1right += 1if resLen == float('inf'):return ""return s[resStart:resStart + resLen]
复杂度分析
时间复杂度: 因为使用变量tInWindow
提前预先保存了window
中是否包含t
的字符,并且只需要遍历一遍s
和t
,所以时间复杂度为O(m + n),其中m
是s
的长度,n
是t
的长度。
空间复杂度: 使用了两个hash
表,具体的复杂度和字符集的大小有关。
相关文章:
备战秋招60天算法挑战,Day15
题目链接: https://leetcode.cn/problems/minimum-window-substring/ 视频题解: https://www.bilibili.com/video/BV1sJ4m1g727/ LeetCode 76. 最小覆盖子串 题目描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s …...

【学习笔记】Matlab和python双语言的学习(整数规划和0-1规划)
文章目录 前言一、整数规划和0-1规划二、典型示例1.背包问题2.指派问题 三、代码实现----Matlab1.Matlab 的 intlinprog 函数2.Matlab 代码背包问题指派问题 四、代码实现----python背包问题指派问题 总结 前言 通过模型算法,熟练对Matlab和python的应用。 学习视频…...

【连续4届EI检索,SPIE 出版】第五届信号处理与计算机科学国际学术会议(SPCS 2024,8月23-25)
第五届信号处理与计算机科学国际学术会议(SPCS 2024) 将于2024年8月23-25日在中国哈尔滨举行。会议主要围绕信号处理与计算机科学等研究领域展开讨论。 会议旨在为从事信号处理与计算机科学研究的专家学者、工程技术人员、技术研发人员提供一个共享科研成果和前沿技…...
Vue屏蔽Console.Log打印信息
Vue屏蔽打印信息 安装 npm install uglifyjs-webpack-plugin --save-dev 在vue.config.js文件或者webpack.prod.conf.js中配置 vue.config中 const UglifyJsPlugin require(uglifyjs-webpack-plugin) // 屏蔽打印数据 module.exports {optimization: {minimizer: [new Ugl…...

数据结构之《二叉树》(下)
在二叉树(中)了解了堆的相关概念后还实现了堆,并且还实现了堆排序,以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构,会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树,接下来就开始本篇的学习吧&…...
用Python打造精彩动画与视频,9.3 项目案例分享与反思
第九章:综合项目 9.3 项目案例分享与反思 在本节中,我们将分享几个成功的项目案例,并进行反思总结。这些案例将展示如何将前面所学的Python技术运用于实际项目中,同时我们将讨论项目中的挑战和解决方案,以及从中得到…...

分布式主键 详解
文章目录 雪花算法结合分库分表的问题问题出现原因分析解决思路 分布式主键要考虑的问题主键生成策略雪花算法详解时间戳位问题工作进程位问题序列号位问题根据雪花算法扩展基因分片法 雪花算法结合分库分表的问题 问题出现 使用ShardingSphere框架自带的雪花算法生成分布式主…...
synchronzed为什么要升级为重量级锁,轻量级锁不好吗?
轻量级锁和重量级锁各有其适用场景和优缺点。轻量级锁旨在减少在无竞争情况下的同步开销,而重量级锁则在竞争激烈的情况下确保线程的同步。以下是为什么在某些情况下需要将轻量级锁升级为重量级锁的原因,以及轻量级锁的不足之处: 为什么需要…...
.NET 项目中发送电子邮件异步处理和错误机制的解决方案
在 .NET 中处理电子邮件,可以使用多种技术和库来实现高效的电子邮件发送、接收和管理。以下是一些常见的解决方案和最佳实践: 目录 1. 使用 SMTP 发送电子邮件 2. 使用 IMAP/POP3 接收电子邮件 3. 异步处理电子邮件 4. 处理大型邮件队列 5. 错误处…...

如何在银河麒麟操作系统上搭建 Electron (含 Electron 打包指南)
本次教程所用版本 Eletron版本:31.3.1 Electron-packager版本:17.1.2 VScode版本:1.92.0 Node版本:18.19.0 npm版本:10.2.3 前言: 随着跨平台应用开发的需求日益增长,Electron 和 Qt 成为…...

小怡分享之数据结构基础知识准备
前言: 🌈✨之前小怡给大家分享了JavaSE的知识,今天小怡要给大家分享一下数据结构基础知识。 一、初识集合框架 1.什么是集合框架 Java集合框架Java Collection Framework, 又称为容器container,是定义在Java.util 包…...
Linux安全与高级应用(三)深入探索MySQL数据库:安装、管理与安全实践
文章目录 深入探索MySQL数据库:安装、管理与安全实践MySQL数据库简介MySQL的安装与配置编译安装MySQL配置MySQL服务 MySQL数据库的基本操作数据库的创建与删除表的创建与管理数据记录的增删改查 MySQL用户管理与权限设置MySQL数据库的备份与恢复数据库备份数据库恢复…...

基于jsp的宠物领养与服务管理系统(源码+论文+部署讲解等)
博主介绍:✌全网粉丝10W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术栈介绍:我是程序员阿龙ÿ…...

基于STM32F407+NBIOT+华为云IOT平台设计的环境检测系统
基于STM32F407NBIOT华为云IOT平台设计的环境检测系统实现的功能: 【1】能够采集本地环境的温度、湿度、烟雾浓度,火光信息,在OLED显示屏上显示。 如果检测到烟雾、温度、火光超过阀值会触发蜂鸣器报警。 【2】能够通过NBIOT将本地设备采集的信…...
工具方法 - 如何表扬小孩子
赞扬小朋友的表现可以通过多种方法来进行,以鼓励他们的积极行为和努力,增强他们的自信心和动力。以下是一些有效的赞扬方法: 1. 具体表扬:指出具体的行为或成就,而不是泛泛地说“你很棒”。例如,“你今天很…...
【扒模块】DySample
逐行注释 import torch import torch.nn as nn import torch.nn.functional as F import warnings# 忽略警告信息,这通常用于开发过程中,避免警告干扰输出结果 warnings.filterwarnings(ignore)# 定义一个函数,用于对神经网络模块的权重进行…...
数学建模之数据分析【四】:变量及其分析
文章目录 一、单变量数据1.1 单变量数据1.2 单变量分析的要点: 二、双变量数据2.1 双变量数据2.2 双变量分析的要点 三、多元数据3.1 多元数据3.2 多元分析的要点 四、单变量,双变量和多变量数据之间的区别 公众号/小红书: 快乐数模 CSDN: 清上尘 本文&a…...

iOS ------ UIKit相关
UIView和CALayer UIView UIView表示屏幕上的一块矩形区域,它是基本上iOS中所有可视化控件的父类。UIView可以管理矩形区域里的内容,处理矩形区域的事件,包括子视图的管理以及动画的实现。 UIKit相关类的继承关系 UIView继承自UIResponde…...

24/8/9算法笔记 随机森林
"极限森林"(Extremely Randomized Trees,简称ERT)是一种集成学习方法,它属于决策树的变体,通常被归类为随机森林(Random Forest)的一种。极限森林的核心思想是在构建决策树时引入极端…...
如何在前后端分离项目中,使用Spring Security
使用 WebSecurityConfigurationAdapter 在前后端分离的架构中,通常使用 Token 进行认证和授权是一种常见的做法。Token 可以是 JSON Web Token(JWT),用于在客户端和服务器之间传递身份信息和访问控制信息。下面我将详细介绍如何在…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...

视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...