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

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

OkHttp 中实现断点续传 demo

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

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...