【算法】滑动窗口—最小覆盖子串
题目
”最小覆盖子串“问题,难度为Hard,题目如下:
给你两个字符串 S 和 T,请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串,则算法返回空串,如果存在这样一个子串,则可以认为答案是唯一的。
比如输入 S = "ADBECFEBANC",T = "ABC",算法应该返回 "BANC"。
如果我们使用暴力解法,代码大概是这样的:
for (int i = 0; i < s.size; i++) {
for (int j = i + 1; j < s.size; j++) {
if [i : j] 包含 t 的所有字母:
更新答案
}
}
思路很简单,但显然不是我们想要的。
滑动窗口思路分析
1.我们在字符串 S 中使用双指针中的左、右指针技巧,初始化 left = right = 0,把索引左闭右开区间 [left, right) 称为一个”窗口“。
2.先不断地增加 right 指针扩大窗口 [left, right),直到窗口中的字符串符合要求(包含了 T 中的所有字符)。
3.此时,停止增加 right,转而不断增加 left 指针缩小窗口 [left, right),直到窗口中的字符串不再符合要求(不包含 T 中所有字符了)。同时,每次增加 left,都要更新一轮结果。
4.重复第2和第3步,直到 right 到达字符 S 的尽头。
第2步相当于在寻找一个”可行解“,然后第3步在优化这个”可行解“,最终找到最优解,也就是最短的覆盖子串。左、右指针轮流前进 ,窗口大小增增减减,窗口不断向右滑动,这就是”滑动窗口“这个名字的来历。
下面画图理解一下这个思路。needs 和 window 相当于计数器,分别记录 T 中字符出现次数和”窗口“中的相应字符的出现次数。
初始状态:

增加 right,直到窗口 [left, right) 包含了 T 中所有字符:

现在开始增加 left,缩小窗口 [left, right):

直到窗口中的字符串不再符合要求,left 不再继续移动:

之后重复上述过程,先移动 right,再移动 left······直到 right 指针到达字符串 S 的末端,算法结束。现在来看看滑动窗口代码框架怎么用。
首先,初始化 window 和 need 两个哈希表,记录窗口中的字符和需要凑齐的字符:
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char key = t.charAt(i);
need.put(key, need.getOrDefault(key, 0) + 1);
}
然后,使用 left 和 right 变量初始化窗口的两端,不要忘了,区间 [left, right) 是左闭右开的,所以初始情况下窗口没有包含任何元素:
int left = 0, right = 0, valid = 0;
while (right < s.length()) { // 开始滑动 }
其中,valid 变量表示窗口中满足 need 条件的字符个数,如果 valid 和 need.size 的大小相同,则说明窗口已满足条件,已经完全覆盖了串 T。
现在开始套模板,只需要思考以下4个问题:
1.当移动 right 扩大窗口,即加入字符时,应该更新哪些数据?
2.什么条件下,窗口应该暂停扩大,开始移动 left 缩小窗口?
3.当移动 left 缩小窗口,即移出字符时,应该更新哪些数据?
4.我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?
一般来说,如果一个字符进入窗口,应该增加 window 计数器;如果一个字符移出窗口,应该减少 window 计数器;当 valid 满足 need 时应该收缩窗口;收缩窗口的时候应该更新最终结果。
下面是完整代码:
package SlidingWindow;import java.util.HashMap;
import java.util.Map;// leetcode 017 最小覆盖子串
public class MCS {public String slidingWindow(String s, String t) {Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();for (int i = 0; i < t.length(); i++) {char key = t.charAt(i);need.put(key, need.getOrDefault(key, 0) + 1);}int left = 0, right = 0, valid = 0; // valid 表示窗口中满足 need 条件的字符个数// 记录最小覆盖子串的启始索引及长度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.getOrDefault(c, 0).equals(need.getOrDefault(c, 0))) { // window[c] == need[c]valid++;}}/*** debug 输出的位置***/System.out.println("window:(" + left + ", " + right + ")");/*********************/// 判断左侧窗口是否要收缩while (valid == need.size()) { // window need shrink —窗口需要收缩// 在这里更新最小覆盖子串if (right - left < len) {start = left;len = right - left;}// d 是将要移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 进行窗口内数据的一系列更新if (need.containsKey(d)) {if (window.getOrDefault(d, 0).equals(need.getOrDefault(d, 0))) {valid--;}window.put(d, window.getOrDefault(d, 0) - 1);}}}// 返回最小覆盖子串return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len); // s.substring(start, start + len) == C++ 中的 s.substr(start, len)}public static void main(String[] args) {MCS mcs = new MCS();String str = mcs.slidingWindow("ADOBECODEBANC", "ABC");System.out.println(str);}}
相关文章:
【算法】滑动窗口—最小覆盖子串
题目 ”最小覆盖子串“问题,难度为Hard,题目如下: 给你两个字符串 S 和 T,请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串,则算法返回空串,如果存在这样一个子串,则可…...
“Fast-forward“ in git-pull result
当你执行 git pull 并且结果显示 Fast-forward 时,这意味着你的本地分支可以直接快进到远程分支的最新提交,没有任何冲突或者需要合并的内容。具体来说,Fast-forward 是一种合并方式,它的特点是将当前分支的指针直接移动到远程分支…...
Oracle(133)如何创建表空间(Tablespace)?
在Oracle数据库中,表空间(Tablespace)是存储数据的逻辑单位,它由一个或多个数据文件组成。表空间是数据库数据管理的基本结构,了解如何创建表空间对于数据库管理员至关重要。 创建表空间的基本语法 创建表空间的基本…...
Linux中权限和指令
💥1、Linux基本指令 1.1 mv 指令 mv指令是move的缩写,用来移动或重命名文件、目录,经常用来备份文件或目录。 mv old_name new_name: 重命名文件或目录mv file /path/to/directory: 移动文件到指定目录 roothcss-ecs…...
本地镜像发布到阿里云
本地镜像发布到阿里云 登录阿里云容器镜像服务配置 Docker 登录阿里云容器镜像服务标记你的 Docker 镜像推送镜像到阿里云验证使用阿里云镜像注意事项 将 Docker 本地镜像发布到阿里云(Alibaba Cloud)容器镜像服务(Container Registry&#x…...
【Linux】【Vim】Vim 基础
Vim/Gvim 基础 文本编辑基础编辑操作符命令和位移改变文本重复改动Visual 模式移动文本(复制、粘贴)文本对象替换模式 光标移动以 word 为单位移动行首和行尾行内指定单字符移动到匹配的括号光标移动到指定行滚屏简单查找 /string标记 分屏vimdiff 文本编辑 基础编辑 Normal 模…...
计算机人工智能前沿进展-大语言模型方向-2024-09-18
计算机人工智能前沿进展-大语言模型方向-2024-09-18 1. The Application of Large Language Models in Primary Healthcare Services and the Challenges W YAN, J HU, H ZENG, M LIU, W LIANG - Chinese General Practice, 2024 人工智能大语言模型在基层医疗卫生服务中的应…...
ubuntu24安装vivado24(安装并解决若干错误)
目录 安装方法:问题1:解决办法: 问题2:解决方法: 安装完成: 安装方法: 注意:内存最好预留80G空闲的。 安装好大小: 安装依赖库: sudo apt-get update sud…...
CSS实现文本溢出省略号或完整显示
目录 前言1. 省略号2. 完整展示3. Demo 前言 文本内容超出容器宽度的问题,为了保持页面布局的整洁,通常会使用省略号来隐藏多余的内容 一共有两种方式: 设定省略号完整展示 1. 省略号 文本溢出时显示省略号 .item-value {flex-basis: 7…...
three.js PropertyBinding和PropertyMixer
PropertyBinding 对场景图中某一真实属性的引用,内部使用。 构造器 PropertyBinding( rootNode : Object3D, path, parsedPath ) -- rootNode: -- path -- parsedPath (可选) 属性 # .path : Number # .parsedPath : Number # .node : Number # .rootNode …...
ssh远程连接try1账号切换tips
1,创建拥有sudo权限的用户: 在root下 sudo adduser bio sudo vim /etc/sudoers //修改添加如下: bio ALL(ALL) ALL //bio用户就拥有了root权限参考:https://github.com/isLishude/blog/issues/70 2,修改ssh配置 …...
C++之第十二课
课程列表 哎呀呀,失踪人口回归了!(前段时间跑去B站了,久等了) 今天来讲——数组 有一道题是这样的: 有n个数,请输出其中最大的数。 原来我们就要: int a,b,c... 但是——数组…...
Linux硬连接、软连接和复制的区别
硬连接、软连接和复制在Linux系统中的主要区别体现在以下三点: 文件链接的方式文件独立性文件系统的操作上。 一、硬连接 1. 硬连接是通过ln命令创建的,它为文件创建别名,与源文件共享同一inode号码,因此硬连接和源文件实际…...
基于STM32的无人小车自主避障系统设计
文章目录 前言资料获取设计介绍功能介绍设计程序具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设…...
杂牌鼠标侧键设置
X-Mouse Button Control修改侧键基本功能介绍-CSDN博客 下载链接 【X-Mouse汉化版】X-Mouse中文版 v2.19.2 绿色版(支持Win10)-开心电玩 (kxdw.com)...
Android WebView H5 Hybrid 混和开发
对于故乡,我忽然有了新的理解:人的故乡,并不止于一块特定的土地,而是一种辽阔无比的心情,不受空间和时间的限制;这心情一经唤起,就是你已经回到了故乡。——《记忆与印象》 前言 移动互联网发展…...
智源推出下一代检索增强大模型框架MemoRAG
北京智源人工智能研究院与中国人民大学高瓴人工智能学院联合发布了一款创新的人工智能模型框架——MemoRAG。该框架基于长期记忆,旨在推动检索增强生成(RAG)技术的发展,使其能够处理更复杂的任务,而不仅限于简单的问答…...
【AprilTag】视觉定位实战 | 使用 ROS 驱动的 USB 摄像头进行相机标定与 AprilTag 识别
写在前面: 🌟 欢迎光临 清流君 的博客小天地,这里是我分享技术与心得的温馨角落。📝 个人主页:清流君_CSDN博客,期待与您一同探索 移动机器人 领域的无限可能。 🔍 本文系 清流君 原创之作&…...
[数据集][目标检测]俯拍航拍森林火灾检测数据集VOC+YOLO格式6116张2类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):6116 标注数量(xml文件个数):6116 标注数量(txt文件个数):6116 标注…...
windows10下tomcat安装及配置教程
Apache Tomcat是一个开源的、轻量级的Servlet容器,广泛用于运行Java Web应用程序。以下是Tomcat安装及配置的基本步骤,根据搜索结果整理: 一、安装前的准备工作 确保你的计算机上已经安装了Java Development Kit (JDK),因为Tomc…...
千问3.5-2B实战案例:直播截图实时分析→商品链接提取→竞品价格对比→话术生成
千问3.5-2B实战案例:直播截图实时分析→商品链接提取→竞品价格对比→话术生成 1. 项目背景与价值 在电商直播场景中,运营团队面临三个核心痛点: 直播过程中无法实时监测竞品价格动态人工记录商品信息效率低下且容易出错话术调整滞后于市场…...
终极指南:如何用智能工具轻松突破内容访问限制
终极指南:如何用智能工具轻松突破内容访问限制 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 内容访问突破工具是现代数字工作者的必备利器,它能帮助研究人员…...
AI结对编程:与快马AI对话式迭代,智能优化你的系统ER图设计
AI结对编程:与快马AI对话式迭代,智能优化你的系统ER图设计 最近在做一个员工管理系统的数据库设计,发现ER图设计是个需要反复推敲的过程。传统方式下,每次修改都要手动调整图形,效率很低。直到尝试了InsCode(快马)平台…...
**发散创新:策略即代码——用 Rust实现动态权限控制引擎**在现代软件系统中,权限管理早已不是简单的“用
发散创新:策略即代码——用 Rust 实现动态权限控制引擎 在现代软件系统中,权限管理早已不是简单的“用户-角色-资源”映射。越来越多的业务场景要求我们具备灵活、可扩展、易维护的权限决策机制。传统硬编码方式难以应对频繁变更的业务规则,而…...
Phi-3-mini-4k-instruct-gguf多场景落地:跨境电商多语言商品描述批量生成
Phi-3-mini-4k-instruct-gguf多场景落地:跨境电商多语言商品描述批量生成 1. 跨境电商的痛点与解决方案 跨境电商卖家每天面临的最大挑战之一,就是为同一款商品准备不同语言版本的描述。传统做法要么需要雇佣多语种文案人员,要么使用机械的…...
保姆级万物识别教程:阿里开源镜像快速部署,识别图片超简单
保姆级万物识别教程:阿里开源镜像快速部署,识别图片超简单 1. 开篇:为什么选择这个镜像? 今天给大家介绍一个特别实用的AI工具——阿里开源的"万物识别-中文-通用领域"镜像。这个镜像最大的特点就是简单易用ÿ…...
深度解析:基于摄像头的远程生理监测工具箱rPPG-Toolbox实战指南
深度解析:基于摄像头的远程生理监测工具箱rPPG-Toolbox实战指南 【免费下载链接】rPPG-Toolbox rPPG-Toolbox: Deep Remote PPG Toolbox (NeurIPS 2023) 项目地址: https://gitcode.com/gh_mirrors/rp/rPPG-Toolbox 远程生理监测技术正在医疗健康领域引发革命…...
从make clean到build.prop:揭秘Android系统属性生成的完整链条
从make clean到build.prop:揭秘Android系统属性生成的完整链条 当你通过adb shell getprop ro.build.display.id查看设备版本号时,是否好奇过这个字符串背后的生成逻辑?在Android编译系统中,从Makefile执行到最终生成build.prop文…...
MIKE URBAN中污水处理厂如何进行概化
01 前言应用厂网一体化耦合模型研究水厂间调度和厂前溢流入河污染量等内容时,由于不需要关注污水处理厂内部的具体处理工艺,需要对污水处理厂的关键设施进行概化处理。02 水厂资料收集收集污水处理的工艺流程图和设施设计参数。依据厂网一体化模型的研究…...
抖音下载器:从零开始,轻松获取无水印视频的完整指南
抖音下载器:从零开始,轻松获取无水印视频的完整指南 【免费下载链接】douyin-downloader A practical Douyin downloader for both single-item and profile batch downloads, with progress display, retries, SQLite deduplication, and browser fallb…...
