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

76. 最小覆盖子串。优化官方题解!

leetcode原题如下:

        

        给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

        

解题思路---滑动窗口

如何判断当前的窗口包含所有 t 所需的字符呢?我们可以用一个哈希表表示 t 中所有的字符以及它们的个数,用一个哈希表动态维护窗口中所有的字符以及它们的个数,如果这个动态表中包含 t 的哈希表中的所有字符,并且对应的个数都不小于 t 的哈希表中各个字符的个数,那么当前的窗口是「可行」的。

官方题解:

    Map<Character, Integer> ori = new HashMap<Character, Integer>();Map<Character, Integer> cnt = new HashMap<Character, Integer>();public String minWindow(String s, String t) {Map<Character, Integer> ori = new HashMap<>();Map<Character, Integer> cnt = new HashMap<>();// 预处理,初始化 ori 表for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);ori.put(c, ori.getOrDefault(c, 0) + 1);}int l = 0, r = 0;int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;int sLen = s.length();int required = ori.size();  // 需要匹配的字符种类数量int formed = 0;  // 已经匹配的字符种类数量while (r < sLen) {char c = s.charAt(r);cnt.put(c, cnt.getOrDefault(c, 0) + 1);if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {formed++;}while (formed == required && l <= r) {if (r - l + 1 < len) {len = r - l + 1;ansL = l;ansR = l + len;}char leftChar = s.charAt(l);cnt.put(leftChar, cnt.get(leftChar) - 1);if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {formed--;}l++;}r++;}return ansL == -1 ? "" : s.substring(ansL, ansR);}

注意:这里 t 中可能出现重复的字符,所以我们要记录字符的个数。

考虑如何优化? 如果 s=XX⋯XABCXXXX,t=ABC,那么显然 [XX⋯XABC]是第一个得到的「可行」区间,得到这个可行区间后,我们按照「收缩」窗口的原则更新左边界,得到最小区间。我们其实做了一些无用的操作,就是更新右边界的时候「延伸」进了很多无用的 X,更新左边界的时候「收缩」扔掉了这些无用的 X,做了这么多无用的操作,只是为了得到短短的 ABC。没错,其实在 s 中,有的字符我们是不关心的,我们只关心 t中出现的字符,我们可不可以先预处理 s,扔掉那些 t 中没有出现的字符,然后再做滑动窗口呢?也许你会说,这样可能出现 XXABXXC的情况,在统计长度的时候可以扔掉前两个 X,但是不扔掉中间的 X,怎样解决这个问题呢?优化后的时空复杂度又是多少?代码给出优化的版本.

public class MinimumWindowSubstring {public String minWindow(String s, String t) {// 用于记录 t 中各字符需要匹配的次数Map<Character, Integer> ori = new HashMap<>();// 用于记录当前窗口中各字符已匹配的次数Map<Character, Integer> cnt = new HashMap<>();// 预处理,初始化 ori 表for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);ori.put(c, ori.getOrDefault(c, 0) + 1);}int l = 0, r = 0; // 窗口的左右边界int len = Integer.MAX_VALUE; // 记录当前最小窗口的长度int ansL = -1, ansR = -1; // 记录当前最小窗口的左右边界int sLen = s.length(); // 字符串 s 的长度int required = ori.size(); // 需要匹配的字符种类数量int formed = 0; // 已经匹配的字符种类数量// 右指针滑动while (r < sLen) {char c = s.charAt(r);cnt.put(c, cnt.getOrDefault(c, 0) + 1);// 如果当前字符在 ori 表中,并且已匹配次数等于 ori 表中的次数,增加已匹配字符种类数量if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {formed++;}// 左指针滑动,窗口收缩while (formed == required && l <= r) {// 更新最小窗口的长度和边界if (r - l + 1 < len) {len = r - l + 1;ansL = l;ansR = l + len;}// 移动左指针,减少已匹配字符的次数char leftChar = s.charAt(l);cnt.put(leftChar, cnt.get(leftChar) - 1);// 如果左边界字符在 ori 表中,并且减少后的次数小于 ori 表中的次数,减少已匹配字符种类数量if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {formed--;}l++;}// 右指针继续滑动r++;}// 返回最小窗口对应的子串return ansL == -1 ? "" : s.substring(ansL, ansR);}
}

这段代码中的核心思想是使用滑动窗口来找到包含字符串 t 中所有字符的最小窗口。下面是代码中各部分的解释:

  1. oricnt 的初始化:

    • ori 表用于记录字符串 t 中各字符需要匹配的次数。
    • cnt 表用于记录当前窗口中各字符已匹配的次数。
  2. 预处理,初始化 ori 表:

    • 遍历字符串 t,将其中各字符及其需要匹配的次数记录在 ori 表中。
  3. 窗口的左右边界 lr

    • 使用两个指针 lr 来确定窗口。
  4. requiredformed

    • required 记录需要匹配的字符种类数量,即 ori 表的大小。
    • formed 记录已经匹配的字符种类数量,初始为 0。
  5. 右指针滑动(while (r < sLen)):

    • 不断移动右指针 r,直到窗口包含了字符串 s 中的所有字符。
  6. 左指针滑动,窗口收缩(while (formed == required && l <= r)):

    • 移动左指针 l,尝试缩小窗口的大小。
    • 更新最小窗口的长度和边界。
  7. 左右指针继续滑动,直至右指针到达字符串末尾:

相关文章:

76. 最小覆盖子串。优化官方题解!

leetcode原题如下&#xff1a; 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串&#xff0c;则返回空字符串 "" 。 注意&#xff1a; 对于 t 中重复字符&#xff0c;我们寻找的子字符串中该字符数量…...

在国产GPU寒武纪MLU上快速上手Pytorch使用指南

本文旨在帮助Pytorch使用者快速上手使用寒武纪MLU。以代码块为主&#xff0c;文字尽可能简洁&#xff0c;许多部分对标NVIDIA CUDA。不正确的地方请留言更正。本文不定期更新。 文章目录 前言Cambricon PyTorch的Python包torch_mlu导入将模型加载到MLU上model.to(mlu)定义损失函…...

重生奇迹MU觉醒战士攻略

剑士连招技巧&#xff1a;生命之光&#xff1a;PK前起手式&#xff0c;增加血上限。 雷霆裂闪&#xff1a;眩晕住对手&#xff0c;剑士PK战士第一技能&#xff0c;雷霆裂闪是否使用好关系到胜负。 霹雳回旋斩&#xff1a;雷霆裂闪后可以选择用霹雳回旋斩跑出一定范围(因为对手…...

美颜技术详解:深入了解视频美颜SDK的工作机制

本文将深入探讨视频美颜SDK的工作机制&#xff0c;揭示其背后的科技奥秘和算法原理。 1.引言 视频美颜SDK作为一种集成到应用程序中的技术工具&#xff0c;通过先进的算法和图像处理技术&#xff0c;为用户提供令人印象深刻的实时美颜效果。 2.视频美颜SDK的基本工作原理 首…...

3D模型格式转换工具如何实现高性能数据转换?请看CAE系统开发实例!

​ 客户背景 DP Technology是全球知名的CAM的供应商&#xff0c;在全球8个国家设有18个办事处。DP Technology提供的CAMESPRIT系统是一个用于数控编程&#xff0c;优化和仿真全方面的CAM系统。CAMESPRIT的客户来自多个行业&#xff0c;因此支持多种CAD工具和文件格式显得格外重…...

多级缓存:亿级流量的缓存方案

文章目录 一.多级缓存的引入二.JVM进程缓存三.Lua语法入门四.多级缓存1.OpenResty2.查询Tomcat3.Redis缓存预热4.查询Redis缓存5.Nginx本地缓存6.缓存同步 一.多级缓存的引入 传统缓存的问题 传统的缓存策略一般是请求到达Tomcat后&#xff0c;先查询Redis&#xff0c;如果未…...

C语言——高精度乘法

一、引子 高精度乘法相较于高精度加法和减法有更多的不同&#xff0c;加法和减法是一位对应一位进行操作的&#xff0c;而乘法是一个数的每一位对另一个数的每一位进行操作&#xff0c;需要的计算步骤更多。 二、核心算法 void Calculate(int num1[], int num2[], int numres…...

为什么C语言没有被C++所取代呢?

今日话题&#xff0c;为什么C语言没有被C所取代呢&#xff1f;虽然C是一个功能更强大的语言&#xff0c;但C语言在嵌入式领域仍然广泛使用&#xff0c;因为它更轻量级、更具可移植性&#xff0c;并且更适合在资源受限的环境中工作。这就是为什么C语言没有被C所取代的原因。如果…...

基于Spring的枚举类+策略模式设计(以实现多种第三方支付功能为例)

摘要 最近阅读《贯彻设计模式》这本书&#xff0c;里面使用一个更真实的项目来介绍设计模式的使用&#xff0c;相较于其它那些只会以披萨、厨师为例的设计模式书籍是有些进步。但这书有时候为了使用设计模式而强行朝着对应的 UML 图来设计类结构&#xff0c;并且对设计理念缺少…...

基于Linphone android sdk开发Android软话机

1.Linphone简介 1.1 简介 LinPhone是一个遵循GPL协议的开源网络电话或者IP语音电话&#xff08;VOIP&#xff09;系统&#xff0c;其主要如下。使用linphone&#xff0c;开发者可以在互联网上随意的通信&#xff0c;包括语音、视频、即时文本消息。linphone使用SIP协议&#…...

[论文分享]TimeDRL:多元时间序列的解纠缠表示学习

论文题目&#xff1a;TimeDRL: Disentangled Representation Learning for Multivariate Time-Series 论文地址&#xff1a;https://arxiv.org/abs/2312.04142 代码地址&#xff1a;暂无 关键要点&#xff1a;多元时间序列&#xff0c;自监督表征学习&#xff0c;分类和预测 摘…...

分享一个好看的vs主题

最近发现了一个很好看的vs主题&#xff08;个人认为挺好看的&#xff09;&#xff0c;想要分享给大家。 主题的名字叫NightOwl&#xff0c;和vscode的主题颜色挺像的。操作方法也十分简单&#xff0c;首先我们先在最上面哪一行找到扩展。 然后点击管理扩展&#xff0c;再搜索栏…...

什么是云呼叫中心?

云呼叫中心作为一种高效的企业呼叫管理方案&#xff0c;越来越受到企业的青睐&#xff0c;常被用于管理客服和销售业务。那么&#xff0c;云呼叫中心到底是什么&#xff1f; 什么是云呼叫中心&#xff1f; 云呼叫中心是一种基于互联网的呼叫管理系统&#xff0c;与传统的呼叫…...

还在用nvm?来试试更快的node版本管理工具——fnm

前言 &#x1f4eb; 大家好&#xff0c;我是南木元元&#xff0c;热衷分享有趣实用的文章&#xff0c;希望大家多多支持&#xff0c;一起进步&#xff01; &#x1f345; 个人主页&#xff1a;南木元元 目录 什么是node版本管理 常见的node版本管理工具 fnm是什么 安装fnm …...

【Hadoop精讲】HDFS详解

目录 理论知识点 角色功能 元数据持久化 安全模式 SecondaryNameNode(SNN) 副本放置策略 HDFS写流程 HDFS读流程 HA高可用 CPA原则 Paxos算法 HA解决方案 HDFS-Fedration解决方案&#xff08;联邦机制&#xff09; 理论知识点 角色功能 元数据持久化 另一台机器就…...

企业需要哪些数字化管理系统?

企业需要哪些数字化管理系统&#xff1f; ✅企业引进管理系统肯定是为了帮助整合和管理大量的数据&#xff0c;从而优化业务流程&#xff0c;提高工作效率和生产力。 ❌但是&#xff0c;如果各个系统之间不互通、无法互相关联数据的话&#xff0c;反而会增加工作量和时间成本…...

【vue】开发常见问题及解决方案

有一些问题不限于 Vue&#xff0c;还适应于其他类型的 SPA 项目。 1. 页面权限控制和登陆验证页面权限控制 页面权限控制是什么意思呢&#xff1f; 就是一个网站有不同的角色&#xff0c;比如管理员和普通用户&#xff0c;要求不同的角色能访问的页面是不一样的。如果一个页…...

飞天使-k8s知识点3-卸载yum 安装的k8s

要彻底卸载使用yum安装的 Kubernetes 集群&#xff0c;您可以按照以下步骤进行操作&#xff1a; 停止 Kubernetes 服务&#xff1a; sudo systemctl stop kubelet sudo systemctl stop docker 卸载 Kubernetes 组件&#xff1a; sudo yum remove -y kubelet kubeadm kubectl…...

ZooKeeper 集群搭建

文章目录 ZooKeeper 概述选举机制搭建前准备分布式配置分布式安装解压缩并重命名配置环境配置服务器编号配置文件 操作集群编写脚本运行脚本搭建过程中常见错误 ZooKeeper 概述 Zookeeper 是一个开源的分布式服务协调框架&#xff0c;由Apache软件基金会开发和维护。以下是对Z…...

Meson:现代的构建系统

Meson是一款现代化、高性能的开源构建系统&#xff0c;旨在提供简单、快速和可读性强的构建脚本。Meson被设计为跨平台的&#xff0c;支持多种编程语言&#xff0c;包括C、C、Fortran、Python等。其目标是替代传统的构建工具&#xff0c;如Autotools和CMake&#xff0c;提供更简…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...