76. 最小覆盖子串
题目链接:力扣

解题思路:滑动窗口
- 因为只需要最小子串中包含t中的所有字符即可,顺序不重要,所以可以先统计一下 t 中每个字符出现的次数,使用map进行统计:
- key表示t中的字符,
- value表示字符的个数:值为正数时表示滑动窗口中需要value个字符,值为负数时表示滑动窗口中多余了 -value个字符
- 初始值:
- result = "":保存最小子串
- num = 0:窗口中包含的 t 中的有效字符个数(如果t中字符a有两个,滑动窗口中已经有两个a了,这个时候右遇到一个a,num并不加1,因为这个a是无效的)
- left = 0:滑动窗口的左边界
- right = 0:滑动窗口的右边界
- 不断左移滑动窗口的右边界,当num==t.length,找到了一个字串包含所有t中的字符,但是这个时候,滑动窗口的左边界可能会有一些无效的字符或者多余的字符:
- 比如 BABC子串,包含t = BC,但是前面的BA是无效的,可以删去,最小子串为BC
- 具体移动过程如下,如果right < s.length,则一直往右移动:
- 如果 map.containsKey(s.charAt(right)):当前字符是 t 中的字符
- 如果map.get(s.charAt(right)) > 0:说明滑动窗口中包含当前字符的个数小于t中的字符个数,令 num++
- map.put(s.charAt(right),map.get(s.charAt(right))-1):令当前字符个数 -1,方便后面缩小滑动窗口的左边界
- 如果 num == t.length:说明滑动窗口中已经包含了所有t中的字符,但这个时候左边界可能有一些不在t中的字符或者多余的字符。需要循环缩小左边界:
- 如果 左边界的字符不在 t中,或者 map.get(s.charAt(left)) < 0,即字符有多余,这两种情况下都需要收缩:
- 如果在t中,并且map中的值小于0,说明左边界这个字符是多余的,令map中的值+1
- left++
- 如果 左边界的字符不在 t中,或者 map.get(s.charAt(left)) < 0,即字符有多余,这两种情况下都需要收缩:
- 如果result.equal("")或者 right - left +1 < result.length():更短的子串
- 令result = s.substring(left,right+1)
- 如果 map.containsKey(s.charAt(right)):当前字符是 t 中的字符
AC代码:
class Solution {public static String minWindow(String s, String t) {char[] sStr = s.toCharArray();char[] tStr = t.toCharArray();Map<Character, Integer> map = new HashMap<>();for (char c : tStr) {map.put(c, map.getOrDefault(c, 0) + 1);}int left = 0;String result = "";//记录滑动窗口中包含多少个t中的字符int num = 0;for (int right = 0; right < sStr.length; right++) {if (map.containsKey(sStr[right])) {if (map.get(sStr[right]) > 0) {num++;}map.put(sStr[right], map.get(sStr[right]) - 1);}if (num == tStr.length) {//缩小窗口右边界while (!map.containsKey(sStr[left]) || map.get(sStr[left]) < 0) {if (map.containsKey(sStr[left])) {map.put(sStr[left], map.get(sStr[left]) + 1);}left++;}if (result.equals("") || right - left + 1 < result.length()) {result = s.substring(left, right + 1);}}}return result;}
}

使用集合进行统计滑动窗口中需要的字符个数或者多余的字符个数,效率较低,可以使用hash表进行优化,思路类似,只不过将map换成hash表:
AC代码
class Solution {public static String minWindow(String s, String t) {char[] sStr = s.toCharArray();char[] tStr = t.toCharArray();int[] hash = new int[128];for (char c : tStr) {hash[c]++;}int left = 0;String result = "";//记录滑动窗口中包含多少个t中的字符int num = 0;for (int right = 0; right < sStr.length; right++) {hash[sStr[right]]--;if (hash[sStr[right]] >= 0) {num++;}while (num == tStr.length && hash[sStr[left]] < 0) {hash[sStr[left++]]++;}if (num == tStr.length && (result.equals("") || right - left + 1 < result.length())) {result = s.substring(left, right + 1);}}return result;}
}

相关文章:
76. 最小覆盖子串
题目链接:力扣 解题思路:滑动窗口 因为只需要最小子串中包含t中的所有字符即可,顺序不重要,所以可以先统计一下 t 中每个字符出现的次数,使用map进行统计: key表示t中的字符,value表示字符的个…...
科兴未来|2023“数智未来,聚放神采”医疗科技创新挑战赛
一、赛事亮点 聚焦前沿神经科学与脑科学领域 展示优质创新产品、技术、平台与服务 汇聚学术端、产业端、投资端多维专业视角 搭建合作交流、产业赋能与生态融合平台 共话行业发展方向与动态趋势 二、赛事简介 2023医疗科技创新挑战赛聚焦于神经科学及脑科学领域的前沿技…...
第56步 深度学习图像识别:CNN梯度权重类激活映射(TensorFlow)
基于WIN10的64位系统演示 一、写在前面 类激活映射(Class Activation Mapping,CAM)和梯度权重类激活映射(Gradient-weighted Class Activation Mapping,Grad-CAM)是两种可视化深度学习模型决策过程的技术…...
云道资本:2023中国氢能源产业-氢制备深度研究报告(附下载)
关于报告的所有内容,公众【营销人星球】获取下载查看 核心观点 中国可再生能源消纳能力提升远远滞后于发电占比的提升。大规模的可再生能源发电是实现碳中和的关键一步,但风电、光伏发电间歌性、波动性强,电网消纳压力较大,且电…...
java文件
一.File类 二.扫描指定目录,并找到名称中包含指定字符的所有普通文件(不包含目录),并且后续询问用户是否要删除该文件 我的代码: import java.io.File; import java.io.IOException; import java.util.Scanner;public class Tes…...
pyqt5 如何终止正在执行的线程?
在 PyQt5 中终止正在执行的线程,可以通过一些协调的方法来实现。一般情况下,直接强行终止线程是不安全的,可能会导致资源泄漏或者程序异常。相反,我们可以使用一种协作的方式,通知线程在合适的时候自行退出。 以下是一…...
力扣第357场周赛补题
6925. 故障键盘 - 力扣(LeetCode) 思路:模拟 class Solution { public:string finalString(string s) {string res;for(auto c : s){if(c i) reverse(res.begin(), res.end());else res c;}return res;} }; 6953. 判断是否能拆分数组 - 力…...
Keras指定model.fit()的输出
model.fit()当verbose1的时候会打印出所有指标和loss, 在多输出的情况下更是一团乱麻. 下面是一个可以指定每个epoch训练完的输入指标的方法: from keras.callbacks import Callback# Custom callback to display loss only at the end of each epoch class LossCallback(Call…...
替换开源LDAP,某科技企业用宁盾目录统一身份,为业务敏捷提供支撑
客户介绍 某高科技企业成立于2015年,是一家深耕于大物流领域的人工智能公司,迄今为止已为全球16个国家和地区,120余家客户打造智能化升级体验,场景覆盖海陆空铁、工厂等货运物流领域。 该公司使用开源LDAP面临的挑战 挑战1 开源…...
解决log4j.xml的url没有注册问题
在对log4j.xml配置文件配置时出现http//jakarta.apache.org/log4j/爆红,IDEA提示uri is not registered。源代码如下 <!DOCTYPE log4j:configuration SYSTEM "log4j.dtd"> <log4j:configuration xmlns:log4j"http://jakarta.apache.org/lo…...
深度思考操作系统面经
1 堆和栈的区别:(如果记的不太清楚,可以类比jvm中的堆和栈的区别,大差不差) 存储位置:堆是在计算机内存中动态分配的区域,而栈是在计算机内存中由操作系统自动分配和管理的区域。管理方式&…...
智慧工地源码:数字孪生智慧工地可视化解决方案
一、智慧工地建设背景 我国经济发展正从传统粗放式的高速增长阶段,进入高效率、低成本、可持续的中高速增长阶段。随着现代建筑的复杂度和体量等不断增加,施工现场管理的内容越来越多,管理的技术难度和要求在不断提高。传统的施工现场管理模…...
解决rockchip平台Android13系统以太网设置静态IP保存不了问题
前言 rk平台平Android13系统测试以太网,发现设置静态IP保存不了问题,即设置静态IP以后重启系统,IP又变成动态的了。 分析 抓取log发现保存静态IP的时候会打印如下log: 08-07 06:22:28.377 626 749 D EthernetNetworkFactory: updateInterface, iface: eth0, ipConfi…...
SQLAlchemy与标准SQL相比有哪些优点?
让我来给你讲讲SQLAlchemy和标准SQL相比有哪些优点吧! 首先,我们要知道,SQLAlchemy是一个Python的SQL工具包和对象关系映射(ORM)系统,它把Python的面向对象编程(OOP)的理念带入了数…...
Zookeeper与Kafka
Zookeeper与Kafka 一、Zookeeper 概述1.Zookeeper 定义2.Zookeeper 工作机制3.Zookeeper 特点4.Zookeeper 数据结构5.Zookeeper 应用场景6.Zookeeper 选举机制 二、部署 Zookeeper 集群1.准备 3 台服务器做 Zookeeper 集群2.安装 Zookeeper3.拷贝配置好的 Zookeeper 配置文件到…...
MySQL—— 基础语法大全
MySQL—— 基础 一、MySQL概述1.1 、数据库相关概念1.2 、MySQL 客户端连接1.3 、数据模型 二、SQL2.1、SQL通用语法2.2、SQL分类2.3、DDL2.4、DML2.5、DQL2.6、DCL 三、函数四、约束五、多表查询六、事务 一、MySQL概述 1.1 、数据库相关概念 数据库、数据库管理系统、SQL&a…...
css小练习:案例6.炫彩加载
一.效果浏览图 二.实现思路 html部分 HTML 写了一个加载动画效果,使用了一个包含多个 <span> 元素的 <div> 元素,并为每个 <span> 元素设置了一个自定义属性 --i。 这段代码创建了一个简单的动态加载动画,由20个垂直排列的…...
使用正则表达式替换文本中的html标签
文章目录 使用正则表达式替换文本中的html标签原文本:使用正则表达式进行替换替换后:展示 html 文本 使用正则表达式替换文本中的html标签 我们存储 markdown 文章时,如果存储转换后的 html 页面,那么在查出来的时候,…...
当向数据库导入大量数据时,mysql主键唯一键重复插入,如何丝滑操作并不导入重复数据呢
解决办法: 答案来源:...
【go-zero】docker镜像直接部署go-zero的API与RPC服务 如何实现注册发现?docker network 实现 go-zero 注册发现
一、场景&问题 使用docker直接部署go-zero微服务会发现API无法找到RPC服务 1、API无法发现RPC服务 用docker直接部署 我们会发现API无法注册发现RPC服务 原因是我们缺少了docker的network网桥 2、系统内查看 RPC服务运行正常API服务启动,通过docker logs 查看日志还是未…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
