LeetCode -- 76. 最小覆盖子串
1. 问题描述
给你一个字符串 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 的子串中,
因此没有符合条件的子字符串,返回空字符串。
2. 思路
题目要求寻找最小连续子串,那么第一个反应就是用滑动窗口求解。滑动窗口移动思路如下:
- 如果当前滑动窗口内没有涵盖t中的所有字符,那么窗口的右侧指针继续向右移动,扩大窗口。
- 如果当前滑动窗口内涵盖了t中的所有字符,那么窗口的左侧指针可以向右移动,缩小窗口,寻找最小子串,直到滑动窗口内无法涵盖t中的所有字符。
移动思路其实比较容易得到,那么还有几个问题:
- 由于t中会有重复字符,因此我们应该记录t中各个字符的数量。拿什么记录?
- 如何判断当前滑动窗口涵盖了t中的所有字符?
我一开始的思路是用HashMap,字符当作key,个数当作value。把字符串t和当前窗口都用两个Map表示。判断当前滑动窗口涵盖了t中的所有字符,就将两个map中的键值对都拿出来一一比较,只要当前窗口Map的value都大于等于t字符串,那就说明涵盖。但这样有个问题,我个人对map的遍历取值操作不太熟悉,而且感觉使用Map有点重,那么有没有别的数据结构可以代替呢?
突然想起来可以用数组,而且数组在存放时也可以达到O(1),在这道题和Map似乎没有差别。思路如下:
由于本题字符串中只有英文字母,因此我可以根据ASCII码,建立一个数组,数组长度就是’A’ - 'a’的值。这样,每一个字符就有固定对应的存放位置,可以保存他出现的次数。还是将字符串t和当前窗口都用两个数组表示。判断当前滑动窗口是否涵盖了t中的所有字符,那就只需要对两个数组进行比较,当前窗口的数组中的每个位置的元素都应该大于等于t字符串。这个操作就很简单了。
3. 代码
public String minWindow(String s, String t) {//滑动窗口的左指针int left = 0;//记录最小字串的长度int minLen = 100001;//记录最小子串的起始位置int start = 0;//t字符串抽象成的数组,保存每一个字符出现的次数int[] tArray = new int[58];for(int i = 0; i < t.length(); i++) {tArray[t.charAt(i) - 'A']++;}//当前滑动窗口抽象成的数组,保存每一个字符出现的次数int[] temp = new int[58];for(int right = 0; right < s.length(); right++) {//先将这个字符加入到滑动窗口中temp[s.charAt(right) - 'A']++;//如果滑动窗口涵盖了字符串twhile(concludeT(temp, tArray)) {//更新最小子串if(minLen > right - left + 1) {minLen = right - left + 1;start = left;}//左指针向右移动temp[s.charAt(left) - 'A']--;left++;}}return minLen == 100001 ? "" : s.substring(start, start + minLen);}//判断当前滑动窗口是否涵盖了t字符串private Boolean concludeT(int[] temp, int[] tArray) {for(int i = 0; i < temp.length; i++) {if(temp[i] < tArray[i]) {return false;}}return true;}
相关文章:
LeetCode -- 76. 最小覆盖子串
1. 问题描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量…...
【进阶五】Python实现SDVRP(需求拆分)常见求解算法——蚁群算法(ACO)
基于python语言,采用经典遗传算法(ACO)对 需求拆分车辆路径规划问题(SDVRP) 进行求解。 目录 往期优质资源1. 适用场景2. 代码调整3. 求解结果4. 代码片段参考 往期优质资源 经过一年多的创作,目前已经成熟…...
php.exe运行时,提示缺少VCRUNTIME140.dll
php.exe运行时,提示缺少VCRUNTIME140.dll 下载地址 https://www.microsoft.com/zh-cn/download/details.aspx?id48145根据需要选择下载3.运行安装后,再次运行php.exe。...
Android垃圾回收机制
1.垃圾回收机制 垃圾回收,也叫GC(Garbage Collection),指的是释放垃圾占用的空间,防止内存泄露。有效的使用可以使用的内存,对内存堆中已经死亡的或者长时间没有使用的对象进行清除和回收。 JVM的内存区域主要分为程序计数器、虚…...
深度学习专家学习计划
深度学习专家学习计划 一、学习背景与目标 作为一名有6年工作经验的Java开发人员,您已具备基本的编程能力和数据处理经验。现计划转岗至深度学习领域,成为深度学习专家。本计划将结合您的工作背景和现有知识,为您制定详细且精确的学习计划,帮助您逐步达到专家水平。 二、…...
关于Ubuntu虚拟机突然上不了网的问题
今天刚重新把Ubuntu虚拟机下回来准备大干一场,结果去吃饭回来虚拟机就上不去网了,具体体现为右上角没有网络的图标,下图是有网络的情况,废话不多说,直接给出解决方案:博客在此 我就是运行了这三行代码就成功…...
[mysql必备面试题]-InnoDB和MyISAM引擎的区别
InnoDB 是 MySQL 默认的事务型存储引擎,只有在需要它不支持的特性时,才考虑使用其它存储引擎。 实现了四个标准的隔离级别,默认级别是可重复读(REPEATABLE READ)。在可重复读隔离级别下,通过多版本并发控制(MVCC) 间隙锁(Next-K…...
android 播放rtsp流的三种方式,2024阿里Android高级面试题总结
使用SurfaceViewMediaPlayer <SurfaceView android:id“id/surface_view” android:layout_width“250dp” android:layout_height“250dp” app:layout_constraintRight_toRightOf“parent” app:layout_constraintTop_toTopOf“parent” /> private String uri …...
unity显示当前时间
1建立文本组件和一个空对象 2创建一个脚本并复制下面代码 using System.Collections; using System.Collections.Generic; using TMPro; using UnityEngine;public class showtime: MonoBehaviour {public TextMeshProUGUI time;private void Update(){string currentTime Sy…...
SDK报错(1)undefined reference to `f_mount‘
利用SDK读取sd卡时,添加了xilffs库,而且包含了ff.h头文件,还是对fat库的函数报错 网上有的说在ARM v7 gcc linker中添加xilffs的方法可以解决,但我试了没有用 最后在赛灵思论坛找到了一个解决方法,原文连接如下 在SDK…...
YOLOv8_pose-Openvino和ONNXRuntime推理【CPU】
纯检测系列: YOLOv5-Openvino和ONNXRuntime推理【CPU】 YOLOv6-Openvino和ONNXRuntime推理【CPU】 YOLOv8-Openvino和ONNXRuntime推理【CPU】 YOLOv7-Openvino和ONNXRuntime推理【CPU】 YOLOv9-Openvino和ONNXRuntime推理【CPU】 跟踪系列: YOLOv5/6/7-O…...
百科 | 光伏电站如何开展运维工作?
从目前太阳能光伏电站的运行管理工作实际经验看,要保证光伏发电系统安全、经济、高效运行,必须建立规范和有效的管理机制,特别是要加强电站的运行维护管理。 一、建立完善的技术文件管理体系 对每个电站都要建立全面完整的技术文件资料档案…...
监听抖音直播间的评论并实现存储
监听抖音直播间评论,主要是动态监听dom元素的变化,如果评论是图片类型的,获取alt的值 主要采用的是MutationObserver:https://developer.mozilla.org/zh-CN/docs/Web/API/MutationObserver index.js如下所示:function getPL() {…...
一体机电脑辐射超标整改
电脑一体机是目前台式机和笔记本电脑之间的一个新型的市场产物,它将主机部分、显示器部分整合到一起的新形态电脑,该产品的创新在于内部元件的高度集成。随着无线技术的发展,电脑一体机的键盘、鼠标与显示器可实现无线链接,机器只…...
重学SpringBoot3-路径匹配机制
更多SpringBoot3内容请关注我的专栏:《SpringBoot3》 期待您的点赞👍收藏⭐评论✍ 重学SpringBoot3-路径匹配机制 AntPathMatcherPathPatternParser 和 PathPattern演示AntPathMatcher 示例PathPattern 示例性能和精确度的提升 选择使用哪一种 在 Spring…...
【贪心算法】摆动序列
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 &…...
Unload-labs
function checkFile() {var file document.getElementsByName(upload_file)[0].value;if (file null || file "") {alert("请选择要上传的文件!");return false;}//定义允许上传的文件类型var allow_ext ".jpg|.png|.gif";//提取上传文件的类…...
SRS-220VDC-4Z-10A静态中间继电器 额定电压DC220V 四副转换触点 JOSEF约瑟
系列型号: SRS-24VDC-4Z-8A静态中间继电器;SRS-24VDC-4Z-10A静态中间继电器; SRS-24VDC-4Z-16A静态中间继电器;SRS-24VAC-4Z-8A静态中间继电器; SRS-24VAC-4Z-10A静态中间继电器;SRS-24VAC-4Z-16A静态中…...
解决electron打包vue-element-admin项目页面无法跳转的问题
解决electron打包vue-element-admin项目页面无法跳转的问题 说明之前通过这个教程已经打包成功,但是发现进行账号密码登录后页面无法跳转的问题。现在已经解决,所以记录一下。 1、检查路由模式是否为hash模式,如果不是改成hash模式。 new Ro…...
Uniapp Vue2 image src动态绑定static目录下的图片
报错的static地址写法: this.url ../static/img.png this.url /static/img.png 正确的static地址写法: this.url /static/img.png 动态绑定 <image :src"url"></image>...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
