当前位置: 首页 > 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;用于在客户端和服务器之间传递身份信息和访问控制信息。下面我将详细介绍如何在…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...

写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里

写一个shell脚本&#xff0c;把局域网内&#xff0c;把能ping通的IP和不能ping通的IP分类&#xff0c;并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...

五、jmeter脚本参数化

目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...