算法leetcode|76. 最小覆盖子串(rust重拳出击)


文章目录

  • 76. 最小覆盖子串:
    • 样例 1:
    • 样例 2:
    • 样例 3:
    • 提示:
    • 进阶:
  • 分析:
    • 在这里插入图片描述
  • 题解:
    • rust:
    • go:
    • c++:
    • python:
    • java:


76. 最小覆盖子串:

给你一个字符串 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
  • st 由英文字母组成

进阶:

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


分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • 直接采用双层循环暴力解决的话,时间复杂度会比较高,恐怕过不了用例,没有去试。
  • 题目并不要求字符的顺序,只要求了每种字符的数量,那首先就想到要做计数。
  • 接下来考虑如何降低时间复杂度,每次循环都从新匹配子串是低效的,要尽可能复用,滑动窗口在这里非常合适,使用双指针,先直接移动右指针找到第一个满足条件的子串,记下长度作为备选结果,接下来移动左指针,当不满足覆盖子串的条件时就继续移动右置针直到满足覆盖子串d饿条件,并比较子串的长度,取较小的子串长度作为备选结果,重复该操作,直到循环遍历完毕。
  • 如何高效判断遍历的子串已经满足覆盖子串呢?字符计数这时候就要大展拳脚了,先在遍历字符串 s 之前,先对字符串 t 进行一次遍历,做初始化计数,记录下每种字符的个数(题解中这里使用了减法,使用加法也是可以的,只是后面的加减法就要变),在遍历 s 时,移动右指针就是延长了覆盖子串,同时修改计数,这里的加减法计算要和前面初始化的相反,判断计数是否为0,如果变为0则表示,这种字符的个数已经没有差异了,但是我们需要覆盖了 t 中的每一种字符,所以需要判断 26 个字符的个数是不是都够了,如果都够了,就是满足了覆盖子串,接下来就移动左指针,同时修改计数,这里的加减计算要和右指针移动的相反。
  • 当某个字符的计数变为0时,我们需要判断 26 种字符的字符个数是不是都满足了,这里就需要26次循环,是否有更高效的办法呢?我们可以额外增加一个变量记录有差异的字符种类数(记录有差异的字符数也是可以的,但是后面的逻辑会有一点区别,思想大致相同), 初始化时顺便初始化该变量,在遍历匹配中,每当有字符计数变为0,就修改这个变量,如果这个变量变为0则表示完全覆盖,从而提高效率。
  • 只看文字可能不便理解,建议对照着熟悉的语言的题解一起看,希望可以有助学习理解。

在这里插入图片描述

题解:

rust:

impl Solution {pub fn min_window(s: String, t: String) -> String {// 少于目标字符串中数量的字符数量let mut diff_char_count = 0;// 字符计数器let mut cnt = vec![0; 128];// 初始化t.as_bytes().iter().for_each(|&b| {// 计数减少cnt[b as usize] -= 1;if cnt[b as usize] == -1 {// 差异字符数增加diff_char_count += 1;}});// 覆盖子串结果信息let (mut ans_len, mut ans_l) = (usize::MAX, usize::MAX);// 开始滑动窗口let s_len = s.len();let (mut l, mut r) = (0, 0);while r < s_len {// 计数增加cnt[s.as_bytes()[r] as usize] += 1;// 向右移动右边界后,可能该字符数量没有差异了if cnt[s.as_bytes()[r] as usize] == 0 {// 差异字符数减少diff_char_count -= 1;// 差异字符数减少后可能为0了if diff_char_count == 0 {// 向右滑动左边界,直到会有差异,取满足要求的最小串while cnt[s.as_bytes()[l] as usize] > 0 {cnt[s.as_bytes()[l] as usize] -= 1;l += 1;}// 更新结果if r - l + 1 < ans_len {ans_len = r - l + 1;ans_l = l;}// 向右移动左边界,差异字符数增加cnt[s.as_bytes()[l] as usize] -= 1;l += 1;diff_char_count += 1;}}r += 1;}return if ans_l == usize::MAX {"".to_string()} else {s[ans_l..ans_l + ans_len].to_string()}}
}

go:

func minWindow(s string, t string) string {// 少于目标字符串中数量的字符数量diffCharCount := 0// 字符计数器cnt := make([]int, 128)// 初始化for _, c := range t {// 计数减少cnt[c]--if cnt[c] == -1 {// 差异字符数增加diffCharCount++}}// 覆盖子串结果信息ansLen, ansL := math.MaxInt32, -1// 开始滑动窗口sLen := len(s)l, r := 0, 0for r < sLen {// 计数增加cnt[s[r]]++// 向右移动右边界后,可能该字符数量没有差异了if cnt[s[r]] == 0 {// 差异字符数减少diffCharCount--// 差异字符数减少后可能为0了if diffCharCount == 0 {// 向右滑动左边界,直到会有差异,取满足要求的最小串for cnt[s[l]] > 0 {cnt[s[l]]--l++}// 更新结果if r-l+1 < ansLen {ansLen = r - l + 1ansL = l}// 向右移动左边界,差异字符数增加cnt[s[l]]--l++diffCharCount++}}r++}if ansL == -1 {return ""} else {return s[ansL : ansL+ansLen]}
}

c++:

class Solution {
public:string minWindow(string s, string t) {// 少于目标字符串中数量的字符数量int diffCharCount = 0;// 字符计数器int cnt[128];memset(cnt, 0, sizeof(cnt));// 初始化const int tLen = t.length();for (int i = 0; i < tLen; ++i) {if (--cnt[t[i]] == -1) {// 差异字符数增加++diffCharCount;}}// 覆盖子串结果信息int ansLen = INT_MAX, ansL = -1;// 开始滑动窗口const int sLen = s.length();int l = 0, r = -1;while (++r < sLen) {// 向右移动右边界后,可能该字符数量没有差异了if (++cnt[s[r]] == 0) {// 差异字符数减少后可能为0了if (--diffCharCount == 0) {// 向右滑动左边界,直到会有差异,取满足要求的最小串while (--cnt[s[l++]] >= 0) {// nothing}// 差异字符数增加++diffCharCount;// 更新结果if (r - l + 2 < ansLen) {ansLen = r - l + 2;ansL = l - 1;}}}}return ansL == -1 ? "" : s.substr(ansL, ansLen);}
};

python:

class Solution:def minWindow(self, s: str, t: str) -> str:# 少于目标字符串中数量的字符数量diff_char_count = 0# 字符计数器cnt = collections.defaultdict(int)# 初始化for c in t:# 计数减少cnt[c] -= 1if cnt[c] == -1:# 差异字符数增加diff_char_count += 1# 覆盖子串结果信息ans_len, ans_l = float("inf"), -1# 开始滑动窗口s_len = len(s)l, r = 0, 0while r < s_len:# 计数增加cnt[s[r]] += 1# 向右移动右边界后,可能该字符数量没有差异了if cnt[s[r]] == 0:# 差异字符数减少diff_char_count -= 1# 差异字符数减少后可能为0了if diff_char_count == 0:# 向右滑动左边界,直到会有差异,取满足要求的最小串while cnt[s[l]] > 0:cnt[s[l]] -= 1l += 1# 更新结果if r - l + 1 < ans_len:ans_len = r - l + 1ans_l = l# 向右移动左边界,差异字符数增加cnt[s[l]] -= 1l += 1diff_char_count += 1r += 1return "" if ans_l == -1 else s[ans_l: ans_l + ans_len]

java:

class Solution {public String minWindow(String s, String t) {// 少于目标字符串中数量的字符数量int diffCharCount = 0;// 字符计数器final int[] cnt = new int[128];// 初始化final int tLen = t.length();for (int i = 0; i < tLen; ++i) {if (--cnt[t.charAt(i)] == -1) {// 差异字符数增加++diffCharCount;}}// 覆盖子串结果信息int ansLen = Integer.MAX_VALUE, ansL = -1;// 开始滑动窗口final int sLen = s.length();int       l    = 0, r = -1;while (++r < sLen) {// 向右移动右边界后,可能该字符数量没有差异了if (++cnt[s.charAt(r)] == 0) {// 差异字符数减少后可能为0了if (--diffCharCount == 0) {// 向右滑动左边界,直到会有差异,取满足要求的最小串while (--cnt[s.charAt(l++)] >= 0) {// nothing}// 差异字符数增加++diffCharCount;// 更新结果if (r - l + 2 < ansLen) {ansLen = r - l + 2;ansL = l - 1;}}}}return ansL == -1 ? "" : s.substring(ansL, ansL + ansLen);}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/120000.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

马斯克谈 Facebook 不开源算法

导读虽然马斯克与扎克伯格的 “八角笼中” 之约没有达成&#xff0c;但很显然&#xff0c;马斯克并不打算就此罢休。既然没能在线下大战一场&#xff0c;那自然不会错过在线上 “出招” 的机会。 他转发了一则推文&#xff0c;并说道&#xff1a;“在地球上&#xff0c;Facebo…

【【萌新的STM32学习25--- USART寄存器的介绍】】

萌新的STM32学习25- USART寄存器的介绍 STM32–USART寄存器介绍&#xff08;F1&#xff09; 控制寄存器1 &#xff08;CR1&#xff09; 位13&#xff1a; 使能USART UE 0&#xff1a; USART分频器和输出被禁止 1&#xff1a; USART模块使能 位12 &#xff1a; 配置8个数据位…

chrono学习(一)

我想用chrono进行沙土的仿真&#xff0c;首先学习demo_GPU_ballCosim.cpp&#xff0c;这个例子仿真了一些沙土的沉降过程。 首先&#xff0c;运行编辑完成的文件demo_GPU_ballCosim&#xff1a; (base) eowyneowyn-MS-7D20:~/build_chrono/bin$ ./demo_GPU_ballCosim 运行完得…

mac常见问题(三) macbook键盘溅上水怎么办?

多朋友在使用mac的时候难免会发生一些小意外&#xff0c;例如说本期要为大家说的macbook键盘溅上水或者其他的液体怎么办&#xff1f;不清楚的同学赶快get这项技能吧&#xff01; 如果你不小心给你的MacBook键盘上溅了水或者其他液体&#xff0c;你需要超级快的把表面的液体清理…

【Java】关于JDK 8的HashMap

文章目录 HashMap 简介数据结构Hash构造方法get(key)方法步骤一&#xff1a;通过key获取所在桶的第一个元素是否存在步骤二:该节点的hash和key是否与要查询的hash和key匹配步骤三:当对应桶中不止一个节点时&#xff0c;根据不同节点类型查询 put(key,value)为什么树化&#xff…

l8-d6 socket套接字及TCP的实现框架

一、socket套接字 /*创建套接字*/ int socket(int domain, int type, int protocol); /*绑定通信结构体*/ int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen); /*监听套接字*/ int listen(int sockfd, int backlog); /*处理客户端发起的连接&#xff0…

WorldCoin 运营数据,业务安全分析

WorldCoin 运营数据&#xff0c;业务安全分析 Worldcoin 的白皮书中声明&#xff0c;Worldcoin 旨在构建一个连接全球人类的新型数字经济系统&#xff0c;由 OpenAI 创始人 Sam Altman 于 2020 年发起。通过区块链技术在 Web3 世界中实现更加公平、开放和包容的经济体系&#…

利用python制作AI图片优化工具

将模糊图片4K高清化效果如下&#xff1a; 优化前的图片 优化后如下图&#xff1a; 优化后图片变大变清晰了效果很明显 软件界面如下&#xff1a; 所用工具和代码&#xff1a; 1、所需软件包 网盘链接&#xff1a;https://pan.baidu.com/s/1CMvn4Y7edDTR4COfu4FviA提取码&…

常用的css样式

1&#xff1a;flex布局 .flex-between {display: flex;justify-content: space-between; }.flex-evenly {display: flex;justify-content: space-evenly; }.flex-end {display: flex;justify-content: flex-end; }.flex {display: flex; }.flex-center {display: flex;justify…

失效的访问控制及漏洞复现

失效的访问控制(越权) 1. 失效的访问控制(越权) 1.1 OWASP TOP10 1.1.1 A5:2017-Broken Access Control 未对通过身份验证的用户实施恰当的访问控制。攻击者可以利用这些缺陷访问未经授权的功能或数据&#xff0c;例如&#xff1a;访问其他用户的帐户、查看敏感文件、修改其…

攻防世界-web2

原题 解题思路 miwen应该是密文的拼音。在函数encode中&#xff0c;传入字符串str&#xff0c;依次将str中的每一个字符转换为十进制ASCII码加一&#xff0c;然后再转换成字符。逆向思路构建代码如下&#xff1a; <?php $miwen"a1zLbgQsCESEIqRLwuQAyMwLyq2L5VwBxqGA…

ES6中导入import导出export

ES6使用 export 和 import 来导出、导入模块 用法 /** 导出 export *///分别导出 export let name 孙悟空; export function sum(a, b) {return a b; } } //先定义再导出 let age 18 export {age}/** 默认导出 export default */const a 默认导出; export default a;/**…

汇编--int指令

中断信息可以来自CPU的内部和外部&#xff0c; 当CPU的内部有需要处理的事情发生的时候&#xff0c;将产生需要马上处理的中断信息&#xff0c;引发中断过程。在http://t.csdn.cn/jihpG&#xff0c;我们讲解了中断过程和两种内中断的处理。 这一章中&#xff0c; 我们讲解另一种…

栈和队列OJ

一、括号的匹配 题目介绍&#xff1a; 思路&#xff1a; 如果 c 是左括号&#xff0c;则入栈 push&#xff1b;否则通过哈希表判断括号对应关系&#xff0c;若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应&#xff0c;则提前返回 false。栈 stack 为空&#xff1…

基于单片机的太阳能热水器控制器设计

一、项目介绍 随着环保意识的逐渐增强&#xff0c;太阳能热水器作为一种清洁能源应用得越来越广泛。然而&#xff0c;传统的太阳能热水器控制器通常采用机械式或电子式温控器&#xff0c;存在精度低、控制不稳定等问题。为了解决这些问题&#xff0c;本项目基于单片机技术设计…

leetcode55.跳跃游戏 【贪心】

题目&#xff1a; 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例…

Rasa 多轮对话机器人

Rasa 开源机器人 目录 Rasa 开源机器人 1. 学习资料 2. Rasa 安装 2.1. rasa 简介 2.2. Rasa系统结构 ​编辑 2.3. 项目的基本流程 ​编辑 2.4. Rasa安装 2.5. 组件介绍 3. Rasa NLU 3.0. NLU 推理输出格式 3.1. 训练数据 ./data/nlu.yml 数据文件 3.2. ./confi…

css3对文字标签不同宽,不同高使用瀑布流对齐显示

<div class"wrapper" style"padding: 0;"><span class"wf-item task-tags text-center" v-for"(item,index) in data.categorys" :key"index">{{ item }}</span> </div>/* 名称瀑布流显示 */ .wrap…

【ES6】js中的__proto__和prototype

在JavaScript中&#xff0c;__proto__和prototype都是用于实现对象继承的关键概念。 1、proto __proto__是一个非标准的属性&#xff0c;用于设置或获取一个对象的原型。这个属性提供了直接访问对象内部原型对象的途径。对于浏览器中的宿主对象和大多数对象来说&#xff0c;可…

Ansible之变量

一&#xff09;Ansible变量介绍 我们在PlayBook⼀节中&#xff0c;将PlayBook类⽐成了Linux中的shell。 那么它作为⼀⻔Ansible特殊的语⾔&#xff0c;肯定要涉及到变量定义、控 制结构的使⽤等特性。 在这⼀节中主要讨论变量的定义和使⽤ 二&#xff09;变量命名规则 变量的…