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

备战秋招60天算法挑战,Day15

题目链接: https://leetcode.cn/problems/minimum-window-substring/

视频题解: https://www.bilibili.com/video/BV1sJ4m1g727/

LeetCode 76. 最小覆盖子串

题目描述

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

注意:

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

举个例子:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

视频题解

最小覆盖子串

思路来源

思路来源

思路解析

本题是经典的滑动窗口类型,解决这类问题的关键是窗口左右边界的滑动策略。

定义hashu_mapT保存字符串t中字符的频率,hashu_mapWindow保存滑动窗口中字符出现的次数,left保存窗口的左边界,right保存窗口的右边界,resStart保存最小候选窗口的起点,resLen保存最小候选窗口长度。

窗口滑动策略如下:

  1. u_mapT中的元素不全在u_mapWindow中,right向右滑动,并更新u_mapWindow[s[right]]++,直到u_mapT中的元素全在u_mapWindow中。
  2. u_mapT中的元素全在u_mapWindow中,left向右滑,并更新u_mapWindow[s[left]]--、最小候选窗口的起点resStart和最小候选窗口长度resLen,直到u_mapT中的元素不全在u_mapWindow中。

根据上面的策略我们可以获得以s任意位置为左边界(枚举左边界)的所有候选窗口,只需要把其中最短的一个窗口返回即可。

这里在判断u_mapT中的元素是否完全在u_mapWindow中并没有采用遍历u_mapT对其中的元素一个个去u_mapWindow中比较。而是借用了一个整型变量tInWindow在窗口滑动的过程中就对窗口中字符情况进行统计,大大节省了每次判断都要去遍历hash表的时间。

C++代码

class Solution {
public:string minWindow(string s, string t) {int s_len = s.length();int t_len = t.length();if (s_len == 0 || t_len == 0) {return "";}//保存t中字符出现的次数unordered_map<char, int> u_mapT;//保存window中的字符出现的次数unordered_map<char, int> u_mapWindow;//统计t中的字符for (int i = 0; i < t_len; ++i) {u_mapT[t[i]]++;}//t中不重复字符的个数int tCount = u_mapT.size();//window完全包含t中不重复字符的数量int tInWindow = 0;int resStart = 0, resLen = INT_MAX;int left = 0, right = 0;while (right < s_len) {u_mapWindow[s[right]]++;//假设字符a在t和window中出现的次数相等,就增加tInWindow的计数if (u_mapT.count(s[right]) && u_mapWindow[s[right]] == u_mapT[s[right]]) {++tInWindow;} while (tInWindow == tCount) {//窗口的大小小于已保存的最小长度,更新最小长度if (right - left + 1 < resLen) {resStart = left;resLen = right - left + 1; }//右移窗口左边界,缩小窗口    u_mapWindow[s[left]]--;if (u_mapT.count(s[left]) && u_mapT[s[left]] > u_mapWindow[s[left]]) {--tInWindow;}++left;}++right;} if (resLen == INT_MAX) return "";return s.substr(resStart, resLen);}
};

java代码

class Solution {public String minWindow(String s, String t) {int s_len = s.length();int t_len = t.length();if (s_len == 0 || t_len == 0) {return "";}//保存t中字符出现的次数Map<Character, Integer> u_mapT = new HashMap<>();//保存window中的字符出现的次数Map<Character, Integer> u_mapWindow = new HashMap<>();//统计t中的字符for (int i = 0; i < t_len; ++i) {u_mapT.put(t.charAt(i), u_mapT.getOrDefault(t.charAt(i), 0) + 1);}//t中不重复字符的个数int tCount = u_mapT.size();//window完全包含t中不重复字符的数量int tInWindow = 0;int resStart = 0, resLen = Integer.MAX_VALUE;int left = 0, right = 0;while (right < s_len) {u_mapWindow.put(s.charAt(right), u_mapWindow.getOrDefault(s.charAt(right), 0) + 1);//假设字符a在t和window中出现的次数相等,就增加tInWindow的计数if (u_mapT.containsKey(s.charAt(right)) && u_mapWindow.get(s.charAt(right)).equals(u_mapT.get(s.charAt(right)))) {++tInWindow;}while (tInWindow == tCount) {//窗口的大小小于已保存的最小长度,更新最小长度if (right - left + 1 < resLen) {resStart = left;resLen = right - left + 1;}//右移窗口左边界,缩小窗口u_mapWindow.put(s.charAt(left), u_mapWindow.get(s.charAt(left)) - 1);if (u_mapT.containsKey(s.charAt(left)) && u_mapWindow.get(s.charAt(left)) < u_mapT.get(s.charAt(left))) {--tInWindow;}++left;}++right;}if (resLen == Integer.MAX_VALUE) return "";return s.substring(resStart, resStart + resLen);}
}

python代码

class Solution:def minWindow(self, s: str, t: str) -> str:s_len = len(s)t_len = len(t)if s_len == 0 or t_len == 0:return ""#保存t中字符出现的次数u_mapT = defaultdict(int)#保存window中的字符出现的次数u_mapWindow = defaultdict(int)#统计t中的字符for char in t:u_mapT[char] += 1#t中不重复字符的个数tCount = len(u_mapT)#window完全包含t中不重复字符的数量tInWindow = 0resStart, resLen = 0, float('inf')left, right = 0, 0while right < s_len:u_mapWindow[s[right]] += 1#假设字符a在t和window中出现的次数相等,就增加tInWindow的计数if s[right] in u_mapT and u_mapWindow[s[right]] == u_mapT[s[right]]:tInWindow += 1while tInWindow == tCount:#窗口的大小小于已保存的最小长度,更新最小长度if right - left + 1 < resLen:resStart = leftresLen = right - left + 1#右移窗口左边界,缩小窗口u_mapWindow[s[left]] -= 1if s[left] in u_mapT and u_mapWindow[s[left]] < u_mapT[s[left]]:tInWindow -= 1left += 1right += 1if resLen == float('inf'):return ""return s[resStart:resStart + resLen]

复杂度分析

时间复杂度: 因为使用变量tInWindow提前预先保存了window中是否包含t的字符,并且只需要遍历一遍st,所以时间复杂度为O(m + n),其中ms的长度,nt的长度。

空间复杂度: 使用了两个hash表,具体的复杂度和字符集的大小有关。

相关文章:

备战秋招60天算法挑战,Day15

题目链接&#xff1a; https://leetcode.cn/problems/minimum-window-substring/ 视频题解&#xff1a; https://www.bilibili.com/video/BV1sJ4m1g727/ LeetCode 76. 最小覆盖子串 题目描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s …...

【学习笔记】Matlab和python双语言的学习(整数规划和0-1规划)

文章目录 前言一、整数规划和0-1规划二、典型示例1.背包问题2.指派问题 三、代码实现----Matlab1.Matlab 的 intlinprog 函数2.Matlab 代码背包问题指派问题 四、代码实现----python背包问题指派问题 总结 前言 通过模型算法&#xff0c;熟练对Matlab和python的应用。 学习视频…...

【连续4届EI检索,SPIE 出版】第五届信号处理与计算机科学国际学术会议(SPCS 2024,8月23-25)

第五届信号处理与计算机科学国际学术会议&#xff08;SPCS 2024) 将于2024年8月23-25日在中国哈尔滨举行。会议主要围绕信号处理与计算机科学等研究领域展开讨论。 会议旨在为从事信号处理与计算机科学研究的专家学者、工程技术人员、技术研发人员提供一个共享科研成果和前沿技…...

Vue屏蔽Console.Log打印信息

Vue屏蔽打印信息 安装 npm install uglifyjs-webpack-plugin --save-dev 在vue.config.js文件或者webpack.prod.conf.js中配置 vue.config中 const UglifyJsPlugin require(uglifyjs-webpack-plugin) // 屏蔽打印数据 module.exports {optimization: {minimizer: [new Ugl…...

数据结构之《二叉树》(下)

在二叉树(中)了解了堆的相关概念后还实现了堆&#xff0c;并且还实现了堆排序&#xff0c;以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构&#xff0c;会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树&#xff0c;接下来就开始本篇的学习吧&…...

用Python打造精彩动画与视频,9.3 项目案例分享与反思

第九章&#xff1a;综合项目 9.3 项目案例分享与反思 在本节中&#xff0c;我们将分享几个成功的项目案例&#xff0c;并进行反思总结。这些案例将展示如何将前面所学的Python技术运用于实际项目中&#xff0c;同时我们将讨论项目中的挑战和解决方案&#xff0c;以及从中得到…...

分布式主键 详解

文章目录 雪花算法结合分库分表的问题问题出现原因分析解决思路 分布式主键要考虑的问题主键生成策略雪花算法详解时间戳位问题工作进程位问题序列号位问题根据雪花算法扩展基因分片法 雪花算法结合分库分表的问题 问题出现 使用ShardingSphere框架自带的雪花算法生成分布式主…...

synchronzed为什么要升级为重量级锁,轻量级锁不好吗?

轻量级锁和重量级锁各有其适用场景和优缺点。轻量级锁旨在减少在无竞争情况下的同步开销&#xff0c;而重量级锁则在竞争激烈的情况下确保线程的同步。以下是为什么在某些情况下需要将轻量级锁升级为重量级锁的原因&#xff0c;以及轻量级锁的不足之处&#xff1a; 为什么需要…...

.NET 项目中发送电子邮件异步处理和错误机制的解决方案

在 .NET 中处理电子邮件&#xff0c;可以使用多种技术和库来实现高效的电子邮件发送、接收和管理。以下是一些常见的解决方案和最佳实践&#xff1a; 目录 1. 使用 SMTP 发送电子邮件 2. 使用 IMAP/POP3 接收电子邮件 3. 异步处理电子邮件 4. 处理大型邮件队列 5. 错误处…...

如何在银河麒麟操作系统上搭建 Electron (含 Electron 打包指南)

本次教程所用版本 Eletron版本&#xff1a;31.3.1 Electron-packager版本&#xff1a;17.1.2 VScode版本&#xff1a;1.92.0 Node版本&#xff1a;18.19.0 npm版本&#xff1a;10.2.3 前言&#xff1a; 随着跨平台应用开发的需求日益增长&#xff0c;Electron 和 Qt 成为…...

小怡分享之数据结构基础知识准备

前言&#xff1a; &#x1f308;✨之前小怡给大家分享了JavaSE的知识&#xff0c;今天小怡要给大家分享一下数据结构基础知识。 一、初识集合框架 1.什么是集合框架 Java集合框架Java Collection Framework&#xff0c; 又称为容器container&#xff0c;是定义在Java.util 包…...

Linux安全与高级应用(三)深入探索MySQL数据库:安装、管理与安全实践

文章目录 深入探索MySQL数据库&#xff1a;安装、管理与安全实践MySQL数据库简介MySQL的安装与配置编译安装MySQL配置MySQL服务 MySQL数据库的基本操作数据库的创建与删除表的创建与管理数据记录的增删改查 MySQL用户管理与权限设置MySQL数据库的备份与恢复数据库备份数据库恢复…...

基于jsp的宠物领养与服务管理系统(源码+论文+部署讲解等)

博主介绍&#xff1a;✌全网粉丝10W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术栈介绍&#xff1a;我是程序员阿龙&#xff…...

基于STM32F407+NBIOT+华为云IOT平台设计的环境检测系统

基于STM32F407NBIOT华为云IOT平台设计的环境检测系统实现的功能&#xff1a; 【1】能够采集本地环境的温度、湿度、烟雾浓度&#xff0c;火光信息&#xff0c;在OLED显示屏上显示。 如果检测到烟雾、温度、火光超过阀值会触发蜂鸣器报警。 【2】能够通过NBIOT将本地设备采集的信…...

工具方法 - 如何表扬小孩子

赞扬小朋友的表现可以通过多种方法来进行&#xff0c;以鼓励他们的积极行为和努力&#xff0c;增强他们的自信心和动力。以下是一些有效的赞扬方法&#xff1a; 1. 具体表扬&#xff1a;指出具体的行为或成就&#xff0c;而不是泛泛地说“你很棒”。例如&#xff0c;“你今天很…...

【扒模块】DySample

逐行注释 import torch import torch.nn as nn import torch.nn.functional as F import warnings# 忽略警告信息&#xff0c;这通常用于开发过程中&#xff0c;避免警告干扰输出结果 warnings.filterwarnings(ignore)# 定义一个函数&#xff0c;用于对神经网络模块的权重进行…...

数学建模之数据分析【四】:变量及其分析

文章目录 一、单变量数据1.1 单变量数据1.2 单变量分析的要点&#xff1a; 二、双变量数据2.1 双变量数据2.2 双变量分析的要点 三、多元数据3.1 多元数据3.2 多元分析的要点 四、单变量&#xff0c;双变量和多变量数据之间的区别 公众号/小红书: 快乐数模 CSDN: 清上尘 本文&a…...

iOS ------ UIKit相关

UIView和CALayer UIView UIView表示屏幕上的一块矩形区域&#xff0c;它是基本上iOS中所有可视化控件的父类。UIView可以管理矩形区域里的内容&#xff0c;处理矩形区域的事件&#xff0c;包括子视图的管理以及动画的实现。 UIKit相关类的继承关系 UIView继承自UIResponde…...

24/8/9算法笔记 随机森林

"极限森林"&#xff08;Extremely Randomized Trees&#xff0c;简称ERT&#xff09;是一种集成学习方法&#xff0c;它属于决策树的变体&#xff0c;通常被归类为随机森林&#xff08;Random Forest&#xff09;的一种。极限森林的核心思想是在构建决策树时引入极端…...

如何在前后端分离项目中,使用Spring Security

使用 WebSecurityConfigurationAdapter 在前后端分离的架构中&#xff0c;通常使用 Token 进行认证和授权是一种常见的做法。Token 可以是 JSON Web Token&#xff08;JWT&#xff09;&#xff0c;用于在客户端和服务器之间传递身份信息和访问控制信息。下面我将详细介绍如何在…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...

Element-Plus:popconfirm与tooltip一起使用不生效?

你们好&#xff0c;我是金金金。 场景 我正在使用Element-plus组件库当中的el-popconfirm和el-tooltip&#xff0c;产品要求是两个需要结合一起使用&#xff0c;也就是鼠标悬浮上去有提示文字&#xff0c;并且点击之后需要出现气泡确认框 代码 <el-popconfirm title"是…...