leetcode76. 最小覆盖子串(滑动窗口-java)
滑动窗口
- 最小覆盖子串
- 滑动窗口
- 代码
- 上期经典
最小覆盖子串
难度 - 困难
原题链接 - 最小覆盖字串
给你一个字符串 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 <= 1e5
s 和 t 由英文字母组成
滑动窗口
这个算法技巧的思路非常简单,就是维护一个窗口,不断滑动,然后更新答案么.
该算法的大致逻辑如下:
int left = 0, right = 0;while (left < right && right < s.size()) {// 增大窗口window.add(s[right]);right++;while (window needs shrink) {// 缩小窗口window.remove(s[left]);left++;}
}
这个算法技巧的时间复杂度是 O(N),比字符串暴力算法要高效得多。
本题的解题思路:
1、我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引左闭右开区间 [left, right) 称为一个「窗口」。
理论上你可以设计两端都开或者两端都闭的区间,但设计为左闭右开区间是最方便处理的。因为这样初始化 left = right = 0 时区间 [0, 0) 中没有元素,但只要让 right 向右移动(扩大)一位,区间 [0, 1) 就包含一个元素 0 了。如果你设置为两端都开的区间,那么让 right 向右移动一位后开区间 (0, 1) 仍然没有元素;如果你设置为两端都闭的区间,那么初始区间 [0, 0] 就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。
2、我们先不断地增加 right 指针扩大窗口 [left, right),直到窗口中的字符串符合要求(包含了 T 中的所有字符)。
3、此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right),直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。
4、重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。
这个思路其实也不难,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解,也就是最短的覆盖子串。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动,这就是「滑动窗口」这个名字的来历。
下面画图理解一下,needs 和 window 相当于计数器,分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。
代码
public String minWindow1(String s, String t) {// 用于记录需要的字符和窗口中的字符及其出现的次数Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();// 统计 t 中各字符出现次数for (char c : t.toCharArray())need.put(c, need.getOrDefault(c, 0) + 1);int left = 0, right = 0;int valid = 0; // 窗口中满足需要的字符个数// 记录最小覆盖子串的起始索引及长度int start = 0, len = Integer.MAX_VALUE;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);// 扩大窗口right++;// 进行窗口内数据的一系列更新if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);if (window.get(c).equals(need.get(c)))valid++; // 只有当 window[c] 和 need[c] 对应的出现次数一致时,才能满足条件,valid 才能 +1}// 判断左侧窗口是否要收缩while (valid == need.size()) {// 更新最小覆盖子串if (right - left < len) {start = left;len = right - left;}// d 是将移出窗口的字符char d = s.charAt(left);// 缩小窗口left++;// 进行窗口内数据的一系列更新if (need.containsKey(d)) {if (window.get(d).equals(need.get(d)))valid--; // 只有当 window[d] 内的出现次数和 need[d] 相等时,才能 -1window.put(d, window.get(d) - 1);}}}// 返回最小覆盖子串return len == Integer.MAX_VALUE ?"" : s.substring(start, start + len);}
上期经典
leetcode59. 螺旋矩阵 II
相关文章:

leetcode76. 最小覆盖子串(滑动窗口-java)
滑动窗口 最小覆盖子串滑动窗口代码 上期经典 最小覆盖子串 难度 - 困难 原题链接 - 最小覆盖字串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t…...
后端项目开发:整合全局异常处理
新建exception目录,用来进行自定义的全局异常处理。 (1)新建自定义的GlobalException基 类继承RuntimeException类,我们自定义的异常类全部需要继承GlobalException基类进行处理。 这里我们直接利用之前定义的错误码接口类。 /…...

Linux socket网络编程概述 和 相关API讲解
socket网络编程的步骤 大体上,连接的建立过程就是:服务器在确定协议类型后,向外广播IP地址和端口号,并监听等待,直到客户端获取了IP地址和端口号并成功连接: 使用socket来进行tcp协议的网络编程的大体步骤…...
uni-app封装省市区下拉组件(后台获取数据)
一.后台数据格式 PROCINCE:[{itemName:,itemValue:}] CITY:[{itemName:,itemValue}] AREA:[{itemName:,itemValue}] 前端将地址数据缓存在了pinia中 前端主要使用picker进行勾选 二.代码 <template><picker change"bindPickerChange" columnchange"…...
laravel中Mail发送邮件失败,但是没有错误信息,该如何调试?
在Laravel中,当使用Mail类发送邮件失败但没有错误信息显示时,可以按照以下步骤进行调试: 检查日志文件: Laravel会记录各种应用程序活动和错误信息。查看应用程序的日志文件,通常位于storage/logs目录下,寻…...
软考高级系统架构设计师系列论文八十五:论软件产品线技术
软考高级系统架构设计师系列论文八十五:论软件产品线技术 一、摘要二、正文三、总结一、摘要 根据“十五”国防科技重点实验室—“机载XXPD火控雷达性能开发与评估实验室”的建设需求。我所在的中国x集团公司x所电子对抗研究部组织了用于该实验室目布式联网试验,主要任务是试…...

More Effective C++学习笔记(4)
目录 条款16:谨记 80 - 20 法则条款17:考虑使用lazy evaluation(缓式评估)条款18:分期摊还预期的计算成本条款19:了解临时对象来源条款20:协助完成 “ 返回值优化 ”条款21:利用重载…...
概率密度函数 累积分布函数
概率密度函数:是指想要求得面积的图形表达式,注意只是表达式,要乘上区间才是概率,所以概率密度并不是概率,而是概率的分布程度。 为什么要引入概率密度,可能是因为连续变量,无法求出某个变量的…...

基于OpenCV实战(基础知识二)
目录 简介 1.ROI区域 2.边界填充 3.数值计算 4.图像融合 简介 OpenCV是一个流行的开源计算机视觉库,由英特尔公司发起发展。它提供了超过2500个优化算法和许多工具包,可用于灰度、彩色、深度、基于特征和运动跟踪等的图像处理和计算机视觉应用。Ope…...

PhantomJS+java 后端生成echart图表的图片
PhantomJSjava 后端生成echart图表的图片 前言源码效果实现echarts-convertPhantomJS实现echarts截图得到图片java延时读取base64数据 参考 前言 该项目仅用作个人学习使用 源码 地址 docker镜像: registry.cn-chengdu.aliyuncs.com/qinjie/java-phantomjs:1.0 …...

vue3 基础知识 ( webpack 基础知识)05
你好 文章目录 一、组件二、如何支持SFC三、webpack 打包工具四、webpack 依赖图五、webpack 代码分包 一、组件 使用组件中我们可以获得非常多的特性: 代码的高亮;ES6、CommonJS的模块化能力;组件作用域的CSS;可以使用预处理器来…...
1.4亿X区智慧城市数字平台及城市大脑(运营中心)建设项目WORD
导读:原文《1.4亿X区智慧城市数字平台及城市大脑(运营中心)建设项目WORD》(获取来源见文尾),本文精选其中精华及架构部分,逻辑清晰、内容完整,为快速形成售前方案提供参考。 部分内…...

wps 画项目进度甘特图
效果如上 步骤一: 创建excel 表格 步骤二: 选中开始时间和结束时间两列数据,右键设置单元格格式 步骤三: 选择数值,点击确定,将日期转成数值。 步骤四:插入图表 选中任务,开始时间…...

【⑭MySQL | 数据类型(二)】字符串 | 二进制类型
前言 ✨欢迎来到小K的MySQL专栏,本节将为大家带来MySQL字符串 | 二进制类型类型的分享✨ 目录 前言5 字符串类型6 二进制类型总结 5 字符串类型 字符串类型用来存储字符串数据,还可以存储图片和声音的二进制数据。字符串可以区分或者不区分大小写的串比…...

Java smslib包开发
上一篇文章我详细介绍RXTXcomm的安装方法和简单代码,如果小伙伴涉及到需要使用手机短信模块完成短信收发需求的话,可以使用到smslib进行开发。 首先还是同样的,将整个smslib包源码导入项目,并且将它所需依赖一起进行导入 导入完成之后,我们就可以对smslib包进行二次开发了 下面…...

职业技术培训内容介绍
泰迪职业技术培训包括:Python技术应用、大数据技术应用、机器学习、大数据分析 、人工智能技术应用。 职业技术培训-Python技术应用 “Python技术应用工程师”职业技术认证是由工业和信息化部教育与考试中心推出一套专业化、科学化、系统化的人才考核标准&…...
AUTOSAR规范与ECU软件开发(实践篇)6.2 ETAS RTA系列工具入门
目录 1、 RTA系列工具安装方法 (1) ETAS RTA-RTE的安装方法 (2) ETAS RTA-BSW的安装方法...

vue3的hooks你可以了解一下
更详细的hooks了解参考这个大佬的文章:掘金:Hooks和Mixins之间的区别 刚开始我简单看了几篇文章感觉Hooks这个东西很普通,甚至感觉还不如vue2的mixin好用。还有export import 感觉和普通定义一个utils文件使用没什么区别。但是Hooks这个东西肯…...

面试之HTTP
1.HTTP与HTTPS的区别 HTTP运行在TCP之上;HTTPS是运行在SSL之上,SSL运行在TCP之上两者使用的端口不同:HTTP使用的是80端口,HTTPS使用的是443端口安全性不同:HTTP没有加密,安全性较差;HTTPS有加密…...

测试框架pytest教程(3)夹具-@pytest.fixture
内置fixture Fixture使用pytest.fixture装饰,pytest有一些内置的fixture 命令可以查看内置fixture pytest --fixtures fixture范围 在pytest中,夹具(fixtures)具有不同的作用范围(scope),用于…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...

Python训练营-Day26-函数专题1:函数定义与参数
题目1:计算圆的面积 任务: 编写一个名为 calculate_circle_area 的函数,该函数接收圆的半径 radius 作为参数,并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求:函数接收一个位置参数 radi…...

GraphRAG优化新思路-开源的ROGRAG框架
目前的如微软开源的GraphRAG的工作流程都较为复杂,难以孤立地评估各个组件的贡献,传统的检索方法在处理复杂推理任务时可能不够有效,特别是在需要理解实体间关系或多跳知识的情况下。先说结论,看完后感觉这个框架性能上不会比Grap…...