(滑动窗口) 76. 最小覆盖子串 ——【Leetcode每日一题】
❓76. 最小覆盖子串
难度:困难
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
注意:
- 对于
t中重复字符,我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2:
输入:s = “a”, t = “a”
输出:“a”
解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
提示:
m == s.lengthn == t.length- 1 < = m , n < = 1 0 5 1 <= m, n <= 10^5 1<=m,n<=105
s和t由英文字母组成
进阶:你能设计一个在 O ( m + n ) O(m+n) O(m+n) 时间 内解决此问题的算法吗?
💡思路:滑动窗口
滑动窗口的思想:
用l和r表示滑动窗口的左边界和 右边界,通过改变l,r来 扩展 和 收缩 滑动窗口,可以想象成一个窗口在字符串上游走,当这个窗口包含的元素满足条件,即包含字符串t的所有元素,记录下这个滑动窗口的长度r - l +1,这些长度中的最小值就是要求的结果。
由于 t 可能包含 重复字符 ,所以使用哈希表 ori 记录 t 中所有的字符以及它们的个数;使用另一个哈希表 cnt 动态维护窗口中所有的字符以及它们的个数。
如果 当前窗口 中包含 t 中所有的字符,且对应的字符个数都不小于 t 的哈希表中各个字符的个数,则当前窗口是「可行」的。此时左边界 l 右移,直到不涵盖 t 中的所有字符,上一个即为满足条件的 当前窗口的最小子串。
使用 distance 记录 当前窗口 中字符 属于 t 对应的个数;当 cnt[s[r]] < ori[s[r]] 时,每增加一个 s[r], distance ++ ,否则 distance 不变。 同理 当 cnt[s[l]] <= ori[s[l]] 每减少一个 s[l], distance -- ,否则 distance 不变。(这样可以在 O ( 1 ) O(1) O(1) 的复杂度判断 当前窗口 内的字符是否符合要求)
具体步骤如下:
- 不断增加
r使滑动窗口 增大,直到窗口包含了t的所有元素; - 不断增加
l使滑动窗口 缩小,因为是要求最小字串,所以将不必要的元素排除在外,使长度减小,直到碰到一个必须包含的元素,这个时候不能再扔了,再扔就不满足条件了,记录此时滑动窗口的长度,并保存最小值; - 让
l再增加一个位置,这个时候滑动窗口肯定不满足条件了,那么继续从 步骤 1 开始执行,寻找新的满足条件的滑动窗口,如此反复,直到r超出了字符串s范围。
🍁代码:(C++、Java)
C++
class Solution {
public:unordered_map <char, int> ori, cnt;string minWindow(string s, string t) {for(const auto &c : t){ //使用哈希表记录t中所有的字符,及其对应的个数++ori[c];}int l = 0, r = -1;int len = INT_MAX, ansl = -1;int distance = 0;while(r < int(s.size())){if(ori.find(s[++r]) != ori.end() && ++cnt[s[r]] <= ori[s[r]] ){//对任何属于t的字符都记录distance++;//记录当前窗口的子串中属于t的字符的个数}while(distance == t.size() && l <= r){//包括所有字符,左指针右移if(r - l + 1 < len){//更新结果len = r - l + 1;ansl = l;}if(ori.find(s[l]) != ori.end() && --cnt[s[l]] < ori[s[l]]){distance--;}++l;}}return ansl == -1 ? string() : s.substr(ansl, len);}
};
Java
class Solution {Map<Character, Integer> ori = new HashMap<Character, Integer>();Map<Character, Integer> cnt = new HashMap<Character, Integer>();public String minWindow(String s, String t) {for(int i = 0; i < t.length(); i++){//使用哈希表记录t中所有的字符,及其对应的个数char c = t.charAt(i);ori.put(c, ori.getOrDefault(c, 0) + 1);}int l = 0, r = -1;int len = Integer.MAX_VALUE, ansl = -1;int distance = 0;while(++r < s.length()){char c = s.charAt(r);if(ori.containsKey(c)){//对任何属于t的字符都记录cnt.put(c, cnt.getOrDefault(c, 0) + 1);if(cnt.get(c) <= ori.get(c)){//记录当前窗口的子串中属于t的字符的个数distance++;}}while(distance == t.length() && l <= r){if(r - l + 1 < len){//更新结果len = r - l + 1;ansl = l;}if(ori.containsKey(s.charAt(l))){cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);if(cnt.get(s.charAt(l)) < ori.get(s.charAt(l))){distance--;}}++l;}}return ansl == -1 ? "" : s.substring(ansl, ansl + len);}
}
🚀 运行结果:

🕔 复杂度分析:
- 时间复杂度: O ( ∣ s ∣ + ∣ t ∣ ) O(∣s∣+∣t∣) O(∣s∣+∣t∣),最坏情况下左右指针对
s的每个元素各遍历一遍,哈希表中对s中的每个元素各插入、删除一次,对t中的元素各插入一次。 - 空间复杂度: O ( C ) O(C) O(C),这里用了两张哈希表作为辅助空间,每张哈希表最多不会存放超过字符集大小的键值对,我们设字符集大小为
C,则渐进空间复杂度为 O ( C ) O(C) O(C)。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:
(滑动窗口) 76. 最小覆盖子串 ——【Leetcode每日一题】
❓76. 最小覆盖子串 难度:困难 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 注意: 对于 t 中重复字符,我们寻找的子字符串…...
grep批量筛选指定目录下的所有日志并写入文件内
背景:在指定目录下,该目录下有上百个日志文件,这些文件以.log结尾 需求:遍历这些日志文件,对每个日志文件进行grep筛选,筛选出包含namexxx和 "server_port":"8088"的内容,并…...
JVM第三讲:JVM 基础-字节码的增强技术详解
JVM 基础-字节码的增强技术详解 本文是JVM第三讲,JVM 基础-字节码的增强技术。在上文中,着重介绍了字节码的结构,这为我们了解字节码增强技术的实现打下了基础。字节码增强技术就是一类对现有字节码进行修改或者动态生成全新字节码文件的技术…...
JWT前后端分离在项目中的应用
14天阅读挑战赛当你累了,要学会休息,而不是放弃! 目录 一、JWT简介 1.1 什么是JWT 1.2 为什么要使用JWT,与session的区别 1.3 JWT组成及工作原理和流程 二、JWT工具类解析 2.1 生成JWT 2.2 解析oldJwt 2.3 复制JWT并延时…...
系统架构师备考倒计时23天(每日知识点)Redis篇
Redis篇 1.Redis与Memcache能力对比 工作MemCacheRedis数据类型简单 key/value 结构丰富的数据结构持久性不支持支持分布式存储客户端哈希分片/一致性哈希多种方式,主从、Sentinel、Cluster 等多线程支持支持支持(Redis5.0及以前版本不支持)内存管理私有内存池/内…...
WIN11系统设置重启与睡眠唤醒后自动拨号
文章目录 1. win x快捷键后选择计算机管理2. 编辑名称3. 选择计算机启动时4. 启动程序5. 输入脚本6. 勾选选项7. 填写配置8. 新建触发器9. 设置触发器10. 确定之后完成创建 1. win x快捷键后选择计算机管理 在任务计划程序中创建基本任务 2. 编辑名称 3. 选择计算机启动时 4…...
【【萌新的SOC学习之AXI-DMA环路测试】】
萌新的SOC学习之AXI-DMA环路测试 AXI DMA环路测试 DMA(Direct Memory Access,直接存储器访问)是计算机科学中的一种内存访问技术。它允许某些计算机内部的硬件子系统可以独立地直接读写系统内存,而不需中央处理器(CPU)介入处理。…...
Lua教程
Lua教程(简单易懂)-CSDN博客 博客相关解释: 5、循环 a {"a", "b"}for i, v in ipairs(a) doprint(i, v)end 代码创建了一个名为 a 的数组,并使用 ipairs 迭代这个数组的元素。运行结果显示了每个元素的索引(下标&am…...
《Node.js+Express+MongoDB+Vue.js全栈开发实战》简介
今天介绍的这本书是《Node.jsExpressMongoDBVue.js全栈开发实战》。该书由清华大学出版社于2023年1月出版 外观 从书名故名思议,就是基于Node.jsExpressMongoDBVue.js来实现企业级应用全栈开发。 封面风格比较简约,插图是一张类似于罗马时代战车形象&…...
多输入多输出 | MATLAB实现CNN-BiGRU-Attention卷积神经网络-双向门控循环单元结合SE注意力机制的多输入多输出预测
多输入多输出 | MATLAB实现CNN-BiGRU-Attention卷积神经网络-双向门控循环单元结合SE注意力机制的多输入多输出预测 目录 多输入多输出 | MATLAB实现CNN-BiGRU-Attention卷积神经网络-双向门控循环单元结合SE注意力机制的多输入多输出预测预测效果基本介绍程序设计往期精彩参考…...
阿里云r7服务器内存型CPU采用
阿里云服务器ECS内存型r7实例是第七代内存型实例规格族,CPU采用第三代Intel Xeon可扩展处理器(Ice Lake),基频2.7 GHz,全核睿频3.5 GHz,计算性能稳定,CPU内存比1:8,2核16G起步&#…...
Godot2D角色导航-自动寻路教程(Godot设置导航代理的目标位置)
文章目录 创建导航NavigationAgent2D节点设置目标位置其他文章 创建导航 首先,创建一个基本的场景,下面的文章讲解了如何创建一个基本的导航场景,点击如下链接前往该文章: Godot2D角色导航-自动寻路教程 NavigationAgent2D节点 …...
R语言实现向量自回归和误差修正模型——附实战代码
大家好,我是带我去滑雪! 向量自回归(VAR)模型和误差修正模型(ECM)是时间序列分析中常用的两种模型,它们用于研究多个变量之间的动态关系。VAR 模型适用于研究多个相关变量之间的相互影响和动态关…...
原理:用UE5制作一个2D游戏
选中资产图片右键--Sprite Actions--Apply Paper2D Texture Settings 制作场景 把它丢到场景里,并把坐标归零 创建图块集tileset 打开新建的tile set,根据最小图块设置最小尺寸单元 选择需要的图块单元,add box 对新建的tile set右键创建til…...
【ARM 嵌入式 编译系列 11.3 -- GCC attribute packed noreturn constructor 介绍】
文章目录 GCC 的 __attribute__ 是一个编译器扩展特性,允许开发者在源代码中设置函数属性(function attributes)、变量属性(variable attributes)和类型属性(type attributes)。这些属性可以影响函数、变量或类型的行为。 以下是一些常见的 __attribute__ 属性: __at…...
主从Reactor高并发服务器
文章目录 Reactor模型的典型分类单Reactor单线程单Reactor多线程多Reactor多线程本项目中实现的主从Reactor One Thread One Loop各模型的优点与缺点 项目分解Reactor服务器模块BufferSocketChannelEpollerTimerWheelEventLoopAnyConnectionAcceptorLoopThreadLoopThreadPoolTc…...
文心一言Plugin实战来了,测试开发旅游攻略助手
刚刚过去的8月,百度WAVE SUMMIT 深度学习开发者大会上,重磅发布文心一言的五个原生插件:百度搜索、览卷文档(基于文档的交互)、E 言易图(数据洞察图表生成)、说图解画(基于图片的交互…...
微服务13-Seata的四种分布式事务模式
文章目录 XA模式实现XA模式 AT模式AT模式的脏写问题(对同数据并发写的问题)其他事务不获取全局锁的一个情况(AT模式写隔离的实现)实现AT模式 TCC模式TCC实现我们怎么样去判断是否空回滚和业务悬挂?业务分析 Saga模式总…...
C结构体内定义结构体,不能直接赋值。
现像: 如下代码: 头文件: typedef struct aBlinkGpioPinOutAbst_{void (*initAsOutput)(void);void (*high)(void);void (*low)(void); }aBlinkGpioPinOutAbst;typedef struct aBlinkGpioAbst_{ #if GPIO_CONFIG_PA0 GPIO_CONFIG_AS_OUTPU…...
PHP遇见错误了看不懂?这些错误提示你必须搞懂
🎬 鸽芷咕:个人主页 🔥 个人专栏:《速学数据结构》 《C语言进阶篇》 ⛺️生活的理想,就是为了理想的生活! 文章目录 一、错误分类二、系统错误:2.1 编译错误2.2 致命错误2.3 警告错误2.4 通知错误 三、用户错误3.1 错…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
ubuntu22.04 安装docker 和docker-compose
首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...
ArcPy扩展模块的使用(3)
管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如,可以更新、修复或替换图层数据源,修改图层的符号系统,甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...
