LeetCode(33)最小覆盖子串【滑动窗口】【困难】

目录
- 1.题目
- 2.答案
- 3.提交结果截图
链接: 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 的子串中,
因此没有符合条件的子字符串,返回空字符串。
提示:
m == s.lengthn == t.length1 <= m, n <= 10^5s和t由英文字母组成
进阶: 你能设计一个在 o(m+n) 时间内解决此问题的算法吗?
2.答案
class Solution {public String minWindow(String s, String t) {// 初始化Map<Character, Integer> tMap = new HashMap<>();char[] tChars = t.toCharArray();for (char tChar : tChars) {tMap.put(tChar, tMap.getOrDefault(tChar, 0) + 1);}// 遍历sint l = 0;int minLength = s.length() + 1;int minL = 0;int minR = 0;char[] sChars = s.toCharArray();Map<Character, Integer> windowMap = new HashMap<>();for (int r = 0; r < sChars.length; r++) {// 右边移动windowMap.put(s.charAt(r), windowMap.getOrDefault(s.charAt(r), 0) + 1);while (checkContains(tMap, windowMap)) {if (r - l + 1 < minLength) {minLength = r - l + 1;minL = l;minR = r;}// 左边移动int count = windowMap.get(s.charAt(l)) - 1;if (count == 0) {windowMap.remove(s.charAt(l));} else {windowMap.put(s.charAt(l), count);}l++;}}return minLength == s.length() + 1 ? "" : s.substring(minL, minR + 1);}private boolean checkContains(Map<Character, Integer> tMap, Map<Character, Integer> window) {for (Map.Entry<Character, Integer> tEntry : tMap.entrySet()) {if (window.getOrDefault(tEntry.getKey(), 0) < tEntry.getValue()) {return false;}}return true;}
}
3.提交结果截图

整理完毕,完结撒花~ 🌻
相关文章:
LeetCode(33)最小覆盖子串【滑动窗口】【困难】
目录 1.题目2.答案3.提交结果截图 链接: 76. 最小覆盖子串 1.题目 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 注意: 对于 t 中重复字…...
设计模式 创建者模式
设计模式 创建者模式 前言原来代码使用设计模式总结Builder模式在源码中的应用:其他代码 前言 “对象创建”模式——绕开new 工厂模式 抽象工厂 原型模式 构建器 动机与背景 目前需要建造一个房子,建造房子需要一系列特定的步骤,但是房子的类…...
排序算法--插入排序
实现逻辑 ① 从第一个元素开始,该元素可以认为已经被排序 ② 取出下一个元素,在已经排序的元素序列中从后向前扫描 ③如果该元素(已排序)大于新元素,将该元素移到下一位置 ④ 重复步骤③,直到找到已排序的元…...
【操作宝典】SQL巨擘:掌握SQL Server Management的终极秘籍!
目录 ⛳️【SQL Server Management】 ⛳️1. 启动登录 ⛳️2. 忘记密码 ⛳️3. 操作数据库和表 3.1 新建数据库text 3.2 新建表 3.3 编辑表 3.4 编写脚本 ⛳️【SQL Server Management】 ⛳️1. 启动登录 需要开启服务 ⛳️2. 忘记密码 登录windows--> 安全性 -->…...
Airtest遇到模拟器无法输入中文的情况该如何处理?
1. 前言 最近有收到同学们的一些提问,使用Airtest的 text 接口,发现在部分模拟器上, text 无法输入中文,不知道该怎么处理。 今天我们就输入这个小问题,来详细聊一下。 2. Airtest的输入法简介 对于Android设备来说…...
从农夫山泉家族任命,看“食企二代”的接班与传承
本文转载自产业科技 农夫山泉再次引发舆论关注,起因是一则人事任命消息。 市场消息称,农夫山泉对区域及人员进行了调整,其总部所在地浙江省被划分为四个区域,在以往浙南、浙北基础上多了浙西大区以及杭州大区,其中农…...
JavaScript启动本地应用程序
JavaScript调起本地应用程序 以下内容,自定义部分我也还未经过实际验证,酌情查看。 文章目录 JavaScript调起本地应用程序确定协议调用协议传参自定义写入协议获取参数 在浏览器中通过 JavaScript调起本地应用程序的一个可行方法就是 通过协议调起。 …...
软件工程理论与实践 (吕云翔)第十四章 软件维护与软件工程管理课后习题与解析
第十四章 软件维护与软件工程管理 1.判断题 (1)代码行技术是比较简单的定量估算软件规模的方法。(√) (2)功能点技术依据对软件信息域特性和软件复杂性的评估结果,估算软件规模。(√) &#…...
Flutter 桌面应用开发之读写Windows注册表
文章目录 需求来源Windows查询Windows版本号方法1. 如何查看Windows版本号2. Windows开发如何通过代码查询Windows版本号(1) 使用C#代码:(2) 使用VB.NET代码 3.通过注册表查看Windows版本信息 Flutter查询Windows版本号方法依赖库支持平台实现步骤1. 在pubspec.yaml…...
【Java Spring】SpringBoot 日志系统
文章目录 一、Spring Boot 日志系统1.1 Spring Boot 日志框架1.2 自定义日志打印1.3 日志级别设置1.4 日志持久化1.5 lombok 简化日志输出 一、Spring Boot 日志系统 1.1 Spring Boot 日志框架 SLF4J 和 logback都是spring boot内置的日志框架,开发者只负责调用对…...
Rust UI开发(四):iced中如何添加菜单栏(串口调试助手)
注:此文适合于对rust有一些了解的朋友 iced是一个跨平台的GUI库,用于为rust语言程序构建UI界面。 这是一个系列博文,本文是第四篇,前三篇链接: 1、Rust UI开发(一):使用iced构建UI时…...
P19 C++ 构造函数的成员初始化列表
目录 前言 01 如果不用成员列表如何初始化变量 02 成员列表初始化 03 为什么要使用成员列表初始化呢? 04 案例代码 前言 本期我们聊聊构造函数初始化列表。 你应该经常使用成员初始化列表,如果你不喜欢这种代码风格,建议你还是慢慢习惯吧…...
acwing算法基础之数学知识--Nim游戏和集合Nim游戏
目录 1 基础知识2 模板3 工程化 1 基础知识 (一) Nim游戏: n n n堆物品,每堆有 a i a_i ai个,两个玩家轮流取走任意一堆的任意个物品,但不能不取。取走最后一个物品的人获胜。 结论:如果这n…...
大数据Doris(二十八):Routine Load查看和修改作业
文章目录 Routine Load查看和修改作业 一、查看导入作业状态...
顺序表总结
📑打牌 : da pai ge的个人主页 🌤️个人专栏 : da pai ge的博客专栏 ☁️宝剑锋从磨砺出,梅花香自苦寒来 目录 🌤️arraylist的简…...
flutter 文本不随系统设置而改变大小[最全的整理]
文本不随系统设置而改变大小[四] 前言方案十九:使用LayoutBuilder和RichText方案二十:使用Transform.scale方案二十一:使用自定义文本缩放因子方案二十二:使用SingleChildScrollView方案二十三:使用FittedBox方案二十四…...
python -opencv 图像锐化
python -opencv 图像锐化 图像锐化其实,是一种增强图片对比度的技术,我们可以通过计算图像的导数,把导数绝对值数值大于零的数值加回原图像,通过这种方法,可以增强图像的对比度。 实现代码如下: import c…...
数字电源为什么一般用DSP控制,而不能用普通的单片机?
数字电源为什么一般用DSP控制,而不能用普通的单片机? 首先你要清楚,数字电源需要一个芯片具备什么功能? 1 能发PWM波 ,并且具备保护关断功能; 电源对PWM发波 要求很高,精度要ns级甚至ps级的&…...
个人投资白银收益怎么样?
个人投资白银是可以带来丰厚的收益,但收益的具体情况取决于多种因素。以下是一些明确的答案和举例,帮助投资者更好地理解个人投资白银的收益情况。 白银市场的价格波动是决定投资收益的主要因素之一,白银价格受全球经济形势、地缘局势风险、…...
代码随想录算法训练营 ---第四十五天
前言: 昨天的题做过之后,今天的题基本上都很简单,但是要注重一下细节。 第一题: 简介: 动态规划五部曲: 1.确定dp数组的含义 dp[i]:爬到有i个台阶的楼顶,有dp[i]种方法 2.确定dp…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
