力扣 最小覆盖子串

ops/2024/9/30 4:26:57/

最小覆盖子串

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/ops/118745.html

相关文章

SpringBoot+Vue项目配置运行通用教程(视频教程)

前提&#xff1a;已安装好项目所需环境 视频教程&#xff1a;点击看视频教程 文字讲解&#xff1a; 解压并导入项目 确定项目的项目运行环境&#xff0c;确保电脑已经全部安装好所需的环境解压项目&#xff0c;并放在没有中文的路径打开 Idea&#xff0c;找到并导入刚刚解压…

yum库 docker的小白安装教程(附部分问题及其解决方案)

yum库 首先我们安装yum 首先在控制台执行下列语句 首先切换到root用户&#xff0c;假如已经是了就不用打下面的语句 su root #使用国内的镜像&#xff0c;不执行直接安装yum是国外的&#xff0c;那个有问题 curl -o /etc/yum.repos.d/CentOS-Base.repo https://mirrors.al…

网络安全:构建数字世界的坚固防线

网络安全&#xff1a;构建数字世界的坚固防线 在21世纪的今天&#xff0c;随着信息技术的飞速发展&#xff0c;互联网已经渗透到我们生活的方方面面&#xff0c;成为现代社会不可或缺的基础设施。从个人日常交流、在线购物、金融服务&#xff0c;到企业的运营管理、数据存储与…

【muduo源码分析】「阻塞」「非阻塞」「同步」「异步」

欢迎来到 破晓的历程的 博客 ⛺️不负时光&#xff0c;不负己✈️ 文章目录 引言何为「muduo库」安装muduo库阻塞、非阻塞、同步、异步数据准备数据准备 引言 从本篇博客开始&#xff0c;我会陆续发表muduo库源码分析的相关文章。感谢大家的持续关注&#xff01;&#xff01;…

viewict小工具使用

本文给大家介绍一个小工具&#xff0c;能够将ict文件图形化显示的方法。这个工具是cadence提供的viewict工具。执行viewict 便能够很直观地看到每一层金属/介电层的情况。 如上图&#xff0c;可以很直观地看到不同金属的厚度&#xff0c;如顶层的alpa_inter为厚金属&#xff0c…

Python 统计学

Python 统计学 Python 是一种广泛使用的编程语言,尤其在数据科学和统计学领域。它提供了丰富的库和工具,使得进行统计分析变得更加容易和高效。本文将介绍 Python 在统计学中的应用,包括基本统计概念、常用的统计函数和库,以及如何使用 Python 进行数据分析。 基本统计概…

three.js 通过着色器实现热力图效果

three.js 通过着色器实现热力图效果 在线预览 https://threehub.cn/#/codeMirror?navigationThreeJS&classifyshader&idheatmapShader 在 https://threehub.cn 中还有很多案例 <!doctype html> <html lang"en"> <head> <meta charse…

C语言编写一个五子棋游戏-代码实例讲解与分析

编写一个完整的五子棋游戏&#xff08;Gomoku 或 Gobang&#xff09;在C语言中是一个相对复杂的任务&#xff0c;因为它涉及到用户界面的处理、游戏逻辑的维护以及可能的AI对手设计。在这里&#xff0c;我将提供一个简化的版本&#xff0c;这个版本将使用控制台来接收用户输入&…