当前位置: 首页 > news >正文

数据结构与算法之字典: Leetcode 76. 最小覆盖子串 (Typescript版)

最小覆盖子串

  • https://leetcode.cn/problems/minimum-window-substring/description/

描述

  • 给你一个字符串 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.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 和 t 由英文字母组成

进阶

  • 你能设计一个在 o(m+n) 时间内解决此问题的算法吗?

算法实现

1 )双指针滑动窗口遍历

function minWindow(s: string, t: string): string {let l = 0;let r = 0;// 维护一个字典,表示子串需要的字符(键)以及长度(值)let m = new Map();// 遍历模板字符串t 用字典存储for(let c of t) {// 这样遍历,可以包含模板字符串t中存在重复的字符m.set(c, m.has(c) ? m.get(c) + 1 : 1);}// 哨兵变量 mSize 用于存储字典中字符的长度let mSize = m.size;// 用于存储输出结果let res = '';while(r < s.length) {let c = s[r];// 如果字典中有该值,那么字典中就不需要了if (m.has(c)) {// 比如s中遇到了A, 在m中有A, 那么在m中A就不再需要了// 如果模板字符串t中含有多个A, 那么此处减少一个Am.set(c, m.get(c) - 1);// 字典中相关字符已经用完if(!m.get(c)) {mSize--;}}// 此处监听mSize是否全部用完while(!mSize) {let newRes = s.substring(l, r + 1);if(!res || newRes.length < res.length) {res = newRes;}// 拿到左指针let c2 = s[l];if(m.has(c2)) {m.set(c2, m.get(c2) + 1);if(m.get(c2) === 1) {mSize ++;}}l++; // 左指针移动}r++; // 右指针移动}return res;
}
  • 解题思路: 先找出所有的包含T的子串,找出长度最小那个子串,返回即可
  • 用双指针维护一个滑动窗口,用于枚举所有子串
  • 移动右指针,找到包含T的子串,移动左指针,尽量减少包含T的子串的长度
  • 循环上述过程,找出包含T的最小子串
  • 时间复杂度:O(m+n) = O(n)
    • m是t的长度
    • n是s的长度,两个while嵌套也是O(n), 就是移动两个指针
  • 空间复杂度:O(m)
    • m是t里不同字符的个数
  • 这个题目难度级别为:困难

相关文章:

数据结构与算法之字典: Leetcode 76. 最小覆盖子串 (Typescript版)

最小覆盖子串 https://leetcode.cn/problems/minimum-window-substring/description/ 描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串&#xff0c;则返回空字符串 “” 。注意&#xff1a; 对于 t 中重…...

2023-10-03 VsCode诡异消失事件

VsCode诡异消失事件 前言一、排查问题二、原因分析三、其它可能不好的倾向总结 前言 今天打开电脑, 习惯性的打开VsCode, 收到错误消息, 该快捷方式所指向的项目Code.exe已经更改或移动, 因此该快捷方式无法正常工作. 是否删除该快捷方式. 一、排查问题 打开快捷方式指向的位…...

elementPlus表格组件el-table实现只能同时选择一行,全选按第一行处理

目录 需求背景&#xff1a; 具体实现&#xff1a; 模板代码&#xff1a; 函数处理代码&#xff1a; 代码讲解&#xff1a; 需求背景&#xff1a; 点击表格最左侧的复选框列&#xff0c;选中当前表格行&#xff0c;而且只允许选择一行&#xff0c;选中一行后&#xff0c;其…...

栈的应用场景(三)

最小栈 1.题目2.画图分析3.代码实现 1.题目 2.画图分析 3.代码实现 package Stack;import java.util.Stack; public class MinStack {private Stack <Integer> stack;private Stack <Integer> MinStack;public MinStack() {stack new Stack<>();MinStack …...

leetCode 45.跳跃游戏 II 贪心算法

45. 跳跃游戏 II - 力扣&#xff08;LeetCode&#xff09; 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: 0 &…...

【MATLAB-基于直方图优化的图像去雾技术】

【MATLAB-基于直方图优化的图像去雾技术】 1 直方图均衡2 程序实现3 局部直方图处理 1 直方图均衡 直方图是图像的一种统计表达形式。对于一幅灰度图像来说&#xff0c;其灰度统计直方图可以反映该图像中不同灰度级出现的统计情况。一般而言&#xff0c;图像的视觉效果和其直方…...

读书笔记|《数据压缩入门》—— 柯尔特·麦克安利斯 亚历克斯·海奇

前言&#xff1a;在接触文本隐写研究领域时了解到这本书。本书可算作《数据压缩》的入门书籍之一&#xff0c;这本书对熵编码、变长编码、统计编码、自适应统计编码、字典编码、上下文编码等常用编码方式的定义及来源进行介绍&#xff0c;对不同场景下不同格式的压缩数据有针对…...

Pandas进阶修炼120题-第五期(一些补充,101-120题)

目录 往期内容&#xff1a;第一期&#xff1a;Pandas基础&#xff08;1-20题&#xff09;第二期&#xff1a;Pandas数据处理&#xff08;21-50题&#xff09;第三期&#xff1a;Pandas金融数据处理&#xff08;51-80题&#xff09;第四期&#xff1a;当Pandas遇上NumPy&#xf…...

NPDP产品经理知识(产品创新管理)

复习文化&#xff0c;团队与领导力 产品创新管理&#xff1a; 如何树立愿景&#xff1a; 如何实现产品战略 计划 实施产品开发&#xff1a; 商业化&#xff0c;营销计划&#xff0c;推广活动 管理产品生命周期&#xff1a; 新式走向市场的流程&#xff1a;...

Flutter+SpringBoot实现ChatGPT流实输出

FlutterSpringBoot实现ChatGPT流式输出、上下文了连续对话 最终实现Flutter的流式输出上下文连续对话。 这里就是提供一个简单版的工具类和使用案例&#xff0c;此处页面仅参考。 服务端 这里直接封装提供工具类&#xff0c;修改自己的apiKey即可使用&#xff0c;支持连续…...

淘宝天猫粉丝福利购店铺优惠券去哪里找到领取网站?

淘宝天猫优惠券去哪里找到领取网站&#xff1f; 领取淘宝天猫粉丝福利购优惠券可通过百度搜索&#xff1a;草柴&#xff0c;进入草柴官方网站 或 手机应用商店搜索&#xff1a;草柴&#xff0c;下载安装草柴APP&#xff0c;就可以领取淘宝天猫优惠券&#xff1b; 草柴APP如何领…...

【考研复习】union有关的输出问题

文章目录 遇到的问题正确解答拓展参考文章 遇到的问题 首次遇到下面的代码时&#xff0c;感觉应该输出65,323。深入理解union的存储之后发现正确答案是&#xff1a;67,323. union {char c;int i; } u; int main(){u.c A;u.i 0x143;printf("%d,%d\n", u.c, u.i); …...

Android学习之路(16) Android 数据库Litepal

一.LitePal的介绍 Litepal是Android郭霖大神的一个开源Android数据库的开源框架&#xff0c;它采用了对象关系映射&#xff08;ORM&#xff09;的模式&#xff0c;这是让我们非常好的理解的数据库&#xff0c;一个实体类对应我们数据库中的一个表。该库中还封装了许多的方法&a…...

Redis持久化(RDB/AOF)

"在哪里走散&#xff0c;你都会 找 到 我。" 认识持久化 我们在接触Mysql事务的时候&#xff0c;一定了解过Mysql事务的四个特性: "原子性(A)一致性(C)隔离性(I)持久性(D)" 而其中持久性其实与持久化是一回事&#xff0c;所谓持久与不持久&#x…...

小谈设计模式(15)—观察者模式

小谈设计模式&#xff08;15&#xff09;—观察者模式 专栏介绍专栏地址专栏介绍 观察者模式核心思想主要角色Subject&#xff08;被观察者&#xff09;ConcreteSubject&#xff08;具体被观察者&#xff09;Observer&#xff08;观察者&#xff09;ConcreteObserver&#xff0…...

简单工厂模式 创建型模式(非GoF经典设计模式)

简单工厂模式是属于创建型模式&#xff0c;也因为工厂中的方法一般设置为静态&#xff0c;又叫做静态工厂方法&#xff08;Static Factory Method&#xff09;模式&#xff0c;但不属于23种GOF设计模式之一。简单工厂模式是由一个工厂对象决定创建出哪一种产品类的实例。简单工…...

PE文件之导入表

1. 导入表 2. 显示导入表信息的例子 ; 作用: 将RVA地址转成FOA即文件偏移 ; 参数: _pFileHdr 指向读到内存中文件的基址指针 ; _dwRVA 目标RVA地址 ; 返回: 目标RVA转成文件偏移的值 RVA2FOA PROC USES esi edi edx, _pFileHdr:PTR BYTE, _dwRVA:DWORDmov esi, _pFil…...

二、码制及其转换

原码 根据我们所学可知&#xff0c;数字电路的逻辑电路是通过输出0和1来表示二进制数的&#xff0c;那么这个二进制数的正负又该怎么表示呢&#xff1f; 答案是在这个二进制数的最高位作为符号位来表示正负性&#xff0c;用0正数&#xff0c;用1表示负数&#xff0c;在这种表达…...

在pycharm中出现下载软件包失败的解决方法

一. 一般情况下我们会选择在设置中下载软件包,过程如下. 1. 直接点击左上角的文件, 再点击设置, 再点击项目, 在右边选择python解释器,点击号,输入要下载的软件包, 在下面的一系列的包中选择相对应的包,点击安装就可以了,有的时候我们下载的是最新的版本,如果要下载固定的版本…...

10.0 探索API调试事件原理

本章笔者将通过Windows平台下自带的调试API接口实现对特定进程的动态转存功能&#xff0c;首先简单介绍一下关于调试事件的相关信息&#xff0c;调试事件的建立需要依赖于DEBUG_EVENT这个特有的数据结构&#xff0c;该结构用于向调试器报告调试事件。当一个程序发生异常事件或者…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL

ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》

近日&#xff0c;嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》&#xff0c;海云安高敏捷信创白盒&#xff08;SCAP&#xff09;成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天&#xff0c;网络安全已成为企业生存与发展的核心基石&#xff0c;为了解…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...