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>...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
鸿蒙HarmonyOS 5军旗小游戏实现指南
1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发,采用DevEco Studio实现,包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...
