最小覆盖子串[困难]
优质博文:IT-BLOG-CN
一、题目
给你一个字符串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.length
n == t.length
1 <= m, n <= 105
s
和t
由英文字母组成
进阶: 你能设计一个在o(m+n)
时间内解决此问题的算法吗?
二、代码
思想: 我们用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针,一个用于「延伸」现有窗口的r
指针,和一个用于「收缩」窗口的l
指针。在任意时刻,只有一个指针运动,而另一个保持静止。我们在s
上滑动窗口,通过移动r
指针不断扩张窗口。当窗口包含t
全部所需的字符后,如果能收缩,我们就收缩窗口直到得到最小窗口。
如何判断当前的窗口包含所有t
所需的字符呢?我们可以用一个哈希表表示t
中所有的字符以及它们的个数,用一个哈希表动态维护窗口中所有的字符以及它们的个数,如果这个动态表中包含t
的哈希表中的所有字符,并且对应的个数都不小于t
的哈希表中各个字符的个数,那么当前的窗口是「可行」的。
注意:这里
t
中可能出现重复的字符,所以我们要记录字符的个数。
优化: 如果s=XX⋯XABCXXXX,t=ABC
,那么显然[XX⋯XABC]
是第一个得到的「可行」区间,得到这个可行区间后,我们按照「收缩」窗口的原则更新左边界,得到最小区间。我们其实做了一些无用的操作,就是更新右边界的时候「延伸」进了很多无用的X
,更新左边界的时候「收缩」扔掉了这些无用的X
,做了这么多无用的操作,只是为了得到短短的ABC
。没错,其实在s
中,有的字符我们是不关心的,我们只关心t
中出现的字符,我们可不可以先预处理s
,扔掉那些t
中没有出现的字符,然后再做滑动窗口呢?也许你会说,这样可能出现XXABXXC
的情况,在统计长度的时候可以扔掉前两个X
,但是不扔掉中间的X
,怎样解决这个问题呢?优化后的时空复杂度又是多少?这里代码给出没有优化的版本。
class Solution {// 1、通过 hashMap 记录 t 中的字符串和个数// 2、通过 fast slow 快慢指针记录最短字符串的位置// 3、通过 hashMap 记录当前符合要求的字符串和个数Map<Character, Integer> ori = new HashMap();// 定义一个变量,保存字串的大小,并将符合要求的字串fast/slow指针赋值给resL,resRint fast = 0, slow = 0, len = Integer.MAX_VALUE, resL = -1, resR = -1;Map<Character, Integer> cur = new HashMap();public String minWindow(String s, String t) {// 4、将需要判断的字串维护在hashMap中for (int i = 0; i < t.length(); i++) {ori.put(t.charAt(i), ori.getOrDefault(t.charAt(i),0) + 1);}// 5、开始遍历s串,通过快慢指针while (fast < s.length() && slow <= fast) {// 6、将s逐个维护在hashMap中cur.put(s.charAt(fast), cur.getOrDefault(s.charAt(fast), 0) + 1);// 7、当新加入字符后,需要判断是否满足最小字串请求,并且小于之前字串的长度while (check(t.length())) {// left 还没有移动,所以下面的判断不能放在 while循环中if ((fast - slow + 1) < len) {len = fast - slow + 1;resL = slow;resR = fast + 1;}// 将cur中slow下标的串-1cur.put(s.charAt(slow), cur.getOrDefault(s.charAt(slow), 0) -1);++slow;}// 循环退出条件++fast;}return resL == -1 ? "" : s.substring(resL, resR);}private boolean check(Integer len) {// 如果 fast 小于 t 的长度,直接返回 falseif (fast < len - 1) {return false;}// 遍历 ori 或者 curIterator iterator = ori.entrySet().iterator();while (iterator.hasNext()) {// 如果 cur 包含该元素,val >= ori.val 则表示成功,否则失败;Map.Entry entry = (Map.Entry)iterator.next();Character key = (Character)entry.getKey();Integer val = (Integer)entry.getValue();// 当前返回的串的个数小于目标串t的个数,说明不符合,直接退出if (cur.getOrDefault(key, 0) < val) {return false;}}return true;}
}
时间复杂度: 最坏情况下左右指针对s
的每个元素各遍历一遍,哈希表中对s
中的每个元素各插入、删除一次,对t
中的元素各插入一次。每次检查是否可行会遍历整个t
的哈希表,哈希表的大小与字符集的大小有关,设字符集大小为C
,则渐进时间复杂度为O(C⋅∣s∣+∣t∣)
)。
空间复杂度: 这里用了两张哈希表作为辅助空间,每张哈希表最多不会存放超过字符集大小的键值对,我们设字符集大小为C
,则渐进空间复杂度为O(C)
。
相关文章:
最小覆盖子串[困难]
优质博文:IT-BLOG-CN 一、题目 给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串,则返回空字符串"" 。 对于t中重复字符,我们寻找的子字符串中该字符数量必须不少于t中该字符数量…...

保姆级搭建Mysql 并进行视图可视化操作
安装MySQL数据库 选择mysql5.7.36_x32.msi”,双击运行,如下图所示: 在此窗口中,选择“Custom”选项,点击“Next>”进入下一步; 在此窗口中,选择号下的MySQL Server 5.7.36 – x64&…...
设计模式的学习顺序
设计模式的学习顺序可以按照以下步骤进行: 掌握基础知识:先确保你对编程语言和软件开发的基本概念有深入的理解,包括面向对象编程、继承、多态等。学习常用设计模式:首先学习并理解一些常用的设计模式,例如单例模式、…...

数据结构和算法——树结构
二叉树 又叫二叉排序树。 节点是数量为,,n为层数。 满二叉树:所有的叶子节点都在最后一层。 完全二叉树:如果所有叶子节点都在最后一层和倒数第二层,而且每个叶子节点都有左右子节点。 完全二叉树 前序遍历 1、先输…...
【Java】Integer包装类
Integer:对基本数据类型 int 实现包装 方法名称说明public Integer(int value)根据 int 值创建 Integer 对象(JDK9以后过时)public integer(String s)根据 String 值创建 Integer 对象…...

Web后端开发登录校验及JWT令牌,过滤器,拦截器详解
如果用户名正确则成功进入 登录功能 代码 Controller Service Mapper 结果 若登录成功结果如下: 如果登录失败,结果如下 登录校验 为什么需要登录校验 有时再未登录情况下, 我们也可以直接访问部门管理, 员工管理等功能 因此我们需要一个登录校验操作, 只有确认用户登录…...

大语言模型迎来重大突破!找到解释神经网络行为方法
前不久,获得亚马逊40亿美元投资的ChatGPT主要竞争对手Anthropic在官网公布了一篇名为《朝向单义性:通过词典学习分解语言模型》的论文,公布了解释经网络行为的方法。 由于神经网络是基于海量数据训练而成,其开发的AI模型可以生成…...

zabbix内置宏、自动发现与注册
一、zabbix内置宏 1、概念: 在Zabbix中,内置宏是一种特殊的变量,通常用在 Trigger 名称和表达式中,引用有关监控对象的信息。 2、种类: {HOST.NAME} 主机名 {HOST.IP} 主机 IP 地址 {TRIGGER.DESCRIPTION} 触…...
Oracle与Mysql语法区别
database 一、数据类型二、update..select语句三、upsert语句四、常见函数五、自动更新列时间戳一、数据类型 OracleMysqlnumberint/decimal变长字符:varchar2varchardatedatetime/timestampinttinyint/smallint/mediumint/int/bigint二、update…select语句 Oracle update t…...

Jetpack:008-Icon与Image
文章目录 1. 概念介绍2. 使用方法2.1 Icon2.2 Image 3. 示例代码4. 内容总结 我们在上一章回中介绍了Jetpack中与Button相关的内容,本章回中主要I con与Image。闲话休提,让我们一起Talk Android Jetpack吧! 1. 概念介绍 我们在本章回中介绍…...

参数解析(牛客)
目录 一、题目 二、代码 一、题目 二、代码 #include <iostream> #include <vector> using namespace std;int main() {string s;getline(cin, s);int i 0;vector<string>ret;while (i < s.size()){if (s[i] )//遇到空格直接跳过{i;}else if (s[i] …...

Linux网络编程系列之服务器编程——阻塞IO模型
Linux网络编程系列 (够吃,管饱) 1、Linux网络编程系列之网络编程基础 2、Linux网络编程系列之TCP协议编程 3、Linux网络编程系列之UDP协议编程 4、Linux网络编程系列之UDP广播 5、Linux网络编程系列之UDP组播 6、Linux网络编程系列之服务器编…...

排序算法-基数排序法(RadixSort)
排序算法-基数排序法(RadixSort) 1、说明 基数排序法与我们之前讨论的排序法不太一样,并不需要进行元素之间的比较操作,而是属于一种分配模式排序方式。 基数排序法比较的方向可分为最高位优先(Most Significant Di…...

nginx绑定tomcat与tomcat联合使用的配置(nginx反向代理tomcat的配置说明)
nginx反向代理tomcat通信配置 (内容来自网上,注解部分才是原创) 切记: url的意思就是 unifed resource location 统一资源定位 其中location就是定位的意思 所以上文中的location就有 对应匹配的 url 标识的资源的相关配置之…...

【Java】nextInt()后面紧接nextLine()读取不到数据/InputMismatchException异常的解决方案
错误如下: 有时候还会抛出InputMismatchException异常 看!我只输入了一个5,并没有给str赋值,它就已经将结果打印出来了!这就意味着,str是读取到了数据的,只不过这个数据并不是我们想要的输入的…...

【传输层协议】UDP/TCP结构特点与原理(详解)
文章目录 1. UDP1.1 UDP结构1.2 UDP特点1. 无连接2. 不可靠3. 面向数据报4. 缓冲区5. 大小受限6. 无序性 2. TCP2.1 TCP结构2.2 TCP特点1. 有连接2. 可靠性3. 面向字节流4. 拥塞控制5. 头部开销 2.3 TCP原理1. 确认应答(安全机制)2. 超时重传(…...
哪种网站适合物理服务器
哪种网站适合物理服务器 看到独立服务器这一词语,相信大家脑海立马就浮现出了它的种种优势,但是有优势就伴随着也有一定的弊端,比如说它的空间大、特殊的的组件配置,权限配置等,但是成本却非常的高,那么我…...

uni-app集成使用SQLite
一、打开uni-app中SQLite 二、封装sqlite.js module.exports {dbName: chat, // 数据库名称dbPath: _doc/chat.db, // 数据库地址,推荐以下划线为开头 _doc/xxx.db/*** Description: 创建数据库 或 有该数据库就打开* author: ZXL* createTime: 2023-10-12 09:23:10* Copyr…...

Qt不能安装自己想要的版本,如Qt 5.15.2
使用在线安装工具安装Qt5.15.2时,发现没有Qt 5的相关版本,只有Qt 6的版本,这时选择右边的Archive,再点击筛选,这时就会出现之前的Qt版本。...

学信息系统项目管理师第4版系列28_组织级项目管理和量化项目管理
1. OPM 1.1. 旨在确保组织开展正确项目并合适地分配关键资源 1.1.1. 有助于确保组织的各个层级都了解组织的战略愿景、实现愿景的措施、组织目标以及可交付成果 1.2. 业务评估是建立OPM框架的必要组件 1.3. OPM3 是组织级项目管理成熟度模型,可用于评估组织项目…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...

2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...