力扣 最小覆盖子串

devtools/2024/9/30 1:51:44/

最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/

题目描述

在这里插入图片描述

题目分析f

覆盖子串:首先根据题意,要求目标字符串的元素必须都在子串中出现过,这表明可以是乱序出现。所以在解决问题是我们需要对子串和目标字符串做匹配,查看子串是否符合要求。
∀ s ∈ S t s . t . s ∈ A n s \begin{align} \forall &s \in \boldsymbol{S_t} \\s.t. \qquad &s \in \boldsymbol{Ans}\end{align} s.t.sStsAns
比较朴素的思路:采用遍历的方法查看是否任意 s ∈ S t s \in \boldsymbol{S_t} sSt都在 A n s \boldsymbol{Ans} Ans
更好的方法:通过某种表示手段表示子串和目标字符串从而判断 A n s \boldsymbol{Ans} Ans是否覆盖 S t \boldsymbol{S_t} St(表示方法判断的复杂度应是 O ( 1 ) O(1) O(1)

题目解决

根据题目提示,确定使用滑动窗口的办法。两个注意点,窗口扩大和窗口缩小
当窗口扩大时注意是否满足条件,当满足条件时尝试缩小窗口。注意每当满足条件时,更新最优窗口大小。

遍历覆盖比较法

当满足覆盖时,缩小窗口,一个个判断
代码

class Solution {
public:bool is_covered(int cnt_s[], int cnt_t[]) {for (int i = 'A'; i <= 'Z'; i++) {if (cnt_s[i] < cnt_t[i]) {return false;}}for (int i = 'a'; i <= 'z'; i++) {if (cnt_s[i] < cnt_t[i]) {return false;}}return true;}string minWindow(string s, string t) {int slen = s.size(), tlen = t.size();string ans;if(slen < tlen) return ans;int ansleft = -1, ansright = slen;int cntwind[128] = {0}, cntt[128]={0};for(char &c : t){++cntt[c];}int left = 0;for(int right = 0; right < slen; ++right){++cntwind[s[right]];while(is_covered(cntwind, cntt)){if(right - left < ansright - ansleft){ansleft = left;ansright = right;}--cntwind[s[left]];++left;}   }return ansleft < 0 ? "" : s.substr(ansleft, ansright - ansleft + 1);}
};

表示覆盖比较法

通过预先设定窗口表示—— C u ( S t ) C_u(S_t) Cu(St)
通过种类,个数的方法表示是否覆盖
实际上通过种类数和个数表示了 S t S_t St,通过维护cntwind、covered_num判断窗口是否覆盖了 S t S_t St
融合了哈希和动归的思想

class Solution {
public:string minWindow(string s, string t) {int slen = s.size(), tlen = t.size();string ans;if(slen < tlen) return ans;int ansleft = -1, ansright = slen;int cntwind[128] = {0};int covered_num = 0;for(char &c : t){if(cntwind[c] == 0){++covered_num;}--cntwind[c];}int left = 0;for(int right = 0; right < slen; ++right){++cntwind[s[right]];if(cntwind[s[right]] == 0) --covered_num;while(covered_num == 0){if(right - left < ansright - ansleft){ansleft = left;ansright = right;}--cntwind[s[left]];if(cntwind[s[left]] < 0) ++covered_num;++left;}   }return ansleft < 0 ? "" : s.substr(ansleft, ansright - ansleft + 1);}
};

总结,巧妙的通过数字的变化表示了窗口状态的变化
++cntwind[s[right]]; if(cntwind[s[right]] == 0) --covered_num;


http://www.ppmy.cn/devtools/118996.html

相关文章

【题解】—— [NOIP2013 普及组] 计数问题

【题解】—— [NOIP2013 普及组] 计数问题 [NOIP2013 普及组] 计数问题题目背景题目描述输入格式输出格式输入输出样例输入 #1输出 #1 提示 1.思路解析2.AC代码 [NOIP2013 普及组] 计数问题 通往洛谷的传送门 题目背景 NOIP2013 普及组 T1 题目描述 试计算在区间 1 1 1 到…

成都睿明智科技有限公司可靠吗?

在这个短视频风靡的时代&#xff0c;抖音已不仅仅是一个娱乐平台&#xff0c;它更是无数商家眼中的蓝海市场&#xff0c;是电商领域的新宠儿。在这场流量与转化的盛宴中&#xff0c;成都睿明智科技有限公司以其敏锐的市场洞察力和专业的服务能力&#xff0c;正逐步成为抖音电商…

【JavaEE初阶】网络原理

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 目录 ⽹络互连 IP地址 端口号 协议 协议分层 优势 TCP/IP 五层网络模型 数据在网络通信中的整体流程 封装和分用 封装 分用 ⽹络互连 随着时代的发展&#xff0c;越来越需…

Linux风险应对策略:保障系统安全的有效措施

Linux作为一种开源操作系统&#xff0c;因其稳定性和安全性被广泛应用于服务器、嵌入式系统和个人电脑等多个领域。然而&#xff0c;随着网络攻击手段的不断演变&#xff0c;Linux系统也面临着各种安全风险。本文将探讨Linux系统的主要风险及其应对策略&#xff0c;帮助用户提升…

python request库的使用

安装和使用 requests库支持python3.8&#xff0c;注意版本 pip install requests 在项目中引用时如下&#xff1a; import requests访问网站 request访问网站一般用get和post两种方式 get requests库提供了get方法&#xff0c;可以用get方式访问网站&#xff0c;相当于在浏览…

揭秘ChatGPT背后的魔法:三阶段训练打造智能对话模型应用

1. 引言 随着自然语言处理技术的快速发展&#xff0c;基于深度学习的大规模预训练模型成为了人工智能领域的重要里程碑。这些大模型能够在广泛的数据上学习&#xff0c;并在不同任务中展现出出色的表现。2022年底释出的ChatGPT正是这种大规模预训练模型的代表性应用&#xff0…

9月27日,每日信息差

第一、中国科学家团队在干细胞治疗领域取得重要突破&#xff0c;通过化学重编程技术成功制备出胰岛细胞&#xff0c;并用于移植治疗一名 1 型糖尿病患者&#xff0c;实现了临床功能性治愈。相关研究成果已发表在国际权威期刊《细胞》上。 第二、交通运输部公路局局长周荣峰在国…

Ubuntu 上安装 Miniconda

一、下载 Miniconda 打开终端。访问 Anaconda 官方仓库下载页面https://repo.anaconda.com/miniconda/选择Miniconda3-py310_24.7.1-0-Linux-x86_64.sh&#xff0c;进行下载。文件名当中的py310_24.7.1表示&#xff0c;在 conda 的默认的 base 环境中的 Python 版本是3.10&…