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>...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!
本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
