贵州省住房和城乡建设官方网站,办公宽带多少钱一年,一个女装店网站建设的策划模板,加盟类网站建设文章目录 C 滑动窗口详解#xff1a;进阶题解与思维分析前言第二章#xff1a;进阶挑战2.1 水果成篮解法一#xff1a;滑动窗口解法二#xff1a;滑动窗口 数组模拟哈希表复杂度分析#xff1a;图解分析#xff1a;示例#xff1a;滑动窗口执行过程图解#xff1a; 详… 文章目录 C 滑动窗口详解进阶题解与思维分析前言第二章进阶挑战2.1 水果成篮解法一滑动窗口解法二滑动窗口 数组模拟哈希表复杂度分析图解分析示例滑动窗口执行过程图解 详细说明 2.2 找到字符串中所有字母异位词解法滑动窗口 哈希表复杂度分析图解分析滑动窗口执行过程图解 详细说明 2.3 串联所有单词的子串解法滑动窗口哈希表复杂度分析图解分析滑动窗口执行过程图解 详细说明 2.4 最小覆盖子串解法滑动窗口 哈希表复杂度分析图解分析滑动窗口执行过程图解 详细说明 写在最后 C 滑动窗口详解进阶题解与思维分析 欢迎讨论如有疑问或见解欢迎在评论区留言互动。 点赞、收藏与分享如觉得这篇文章对您有帮助请点赞、收藏并分享 分享给更多人欢迎分享给更多对 C 感兴趣的朋友一起学习滑动窗口的基础与进阶 前言
接上篇【优选算法篇】编织算法的流动诗篇滑动窗口的轻盈之美 在算法的世界中滑动窗口是一种极具优雅和灵活性的算法技巧。在上一章中我们通过几个经典问题初步领略了滑动窗口的强大之处。然而算法的探索并没有止步于此。随着问题的复杂性逐渐提升滑动窗口的应用场景也变得更加丰富多样。在这篇博客中我们将继续深入探讨滑动窗口的进阶应用。通过更加灵活的策略、动态调整窗口我们将解决一系列复杂的算法挑战进一步揭示滑动窗口的无限可能。 接下来让我们步入滑动窗口的进阶领域探索更多算法之美。 第二章进阶挑战
2.1 水果成篮
题目链接904. 水果成篮
题目描述 你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果种类。你想要尽可能多地收集水果但是有一些规则
你有两个篮子每个篮子只能装一种类型的水果篮子的容量无限制。你可以选择任意一棵树开始采摘但必须从这棵树开始依次向右采摘每棵树上的水果。一旦遇到某棵树上的水果不符合篮子中的水果种类你必须停止采摘。
返回你能采摘的最多的水果数量。
示例 1
输入fruits [1,2,1]输出3解释你可以采摘所有 3 棵树上的水果。
示例 2
输入fruits [0,1,2,2]输出3解释你只能采摘 [1,2,2] 这三棵树的水果。如果从第 1 棵树开始采摘只能采摘到 [0,1]。
示例 3
输入fruits [3,3,3,1,2,1,1,2,3,3,4]输出5解释你可以采摘 [1,2,1,1,2] 这五棵树的水果。
提示
1 fruits.length 1050 fruits[i] fruits.length 解法一滑动窗口
算法思路 本题是典型的滑动窗口问题。要求我们找到一个连续区间其中只能有两种不同种类的水果即至多两个不同元素。通过滑动窗口我们可以动态调整区间大小保持窗口内水果种类不超过两种。 具体步骤
用一个哈希表 hash 记录滑动窗口内的水果种类和数量。滑动窗口的右边界 right 向右移动每次将新水果加入哈希表。如果哈希表中记录的水果种类超过两个左边界 left 开始向右移动直到窗口内水果种类不超过两个为止。在每次满足条件时更新最大收集到的水果数量 ret。
算法流程
初始化哈希表 hash左右指针 left 和 right以及记录结果的变量 ret。遍历数组 fruits对每个水果进行如下操作 将 right 指向的水果加入哈希表统计频次。如果哈希表的大小超过 2左指针 left 向右移动同时更新哈希表直到哈希表中只有两种水果。在满足条件时更新最大采摘数量 ret。 返回结果。 代码实现
#include unordered_map
#include vector
using namespace std;class Solution {
public:int totalFruit(vectorint fruits) {unordered_mapint, int hash; // 统计滑动窗口内水果的种类和数量int ret 0; // 记录最大水果数量int left 0; // 左指针for (int right 0; right fruits.size(); right) {hash[fruits[right]]; // 右指针扩展窗口加入新水果// 如果种类超过 2收缩窗口while (hash.size() 2) {hash[fruits[left]]--; // 移除左边水果if (hash[fruits[left]] 0) {hash.erase(fruits[left]); // 种类为 0删除该水果}left; // 左指针向右移动}ret max(ret, right - left 1); // 更新最大水果数量}return ret;}
};解法二滑动窗口 数组模拟哈希表
算法思路 利用数组 hash 来代替哈希表用水果种类的值直接作为数组下标来统计每种水果的数量。这种方式效率更高因为直接使用数组的下标访问比哈希表操作更快。 代码实现
class Solution {
public:int totalFruit(vectorint fruits) {int hash[100001] {0}; // 数组模拟哈希表int ret 0; // 记录结果int left 0; // 左指针int kinds 0; // 记录当前窗口内的水果种类数for (int right 0; right fruits.size(); right) {if (hash[fruits[right]] 0) kinds; // 新种类水果进入窗口hash[fruits[right]]; // 统计数量// 当水果种类超过 2 时收缩窗口while (kinds 2) {hash[fruits[left]]--; // 移除左边水果if (hash[fruits[left]] 0) kinds--; // 种类数量减少left; // 左指针右移}ret max(ret, right - left 1); // 更新最大水果数量}return ret;}
};复杂度分析
时间复杂度O(n)每个元素最多被左右指针访问两次。空间复杂度O(n)哈希表或数组最多存储 n 种水果的频次。 图解分析
示例
输入fruits [3,3,3,1,2,1,1,2,3,3,4]输出5解释你可以采摘 [1,2,1,1,2] 这五棵树的水果。 滑动窗口执行过程图解
IterationLeftRight水果种类窗口内水果窗口大小最大结果1001[3]112011[3, 3]223021[3, 3, 3]334032[3, 3, 3, 1]445043[3, 3, 3, 1, 2]556352[1, 2, 1]357362[1, 2, 1, 1]458372[1, 2, 1, 1, 2]559782[2, 3]2510792[2, 3, 3]35118102[3, 3, 4]35 详细说明
Iteration 1-3Right 扩展到 2窗口内只有一种水果 3因此子数组为 [3,3,3]长度为 3。Iteration 4加入水果 1种类增加到两种窗口变为 [3,3,3,1]长度更新为 4。Iteration 5加入水果 2种类增加到三种此时需要调整窗口移动 Left直到只剩两种水果。经过调整窗口变为 [1,2,1]。Iteration 6-8继续右移 Right窗口内的水果种类保持为两种最大长度更新为 5子数组为 [1,2,1,1,2]。Iteration 9-11加入水果 3水果种类再次超出限制继续收缩窗口最终找到的最大子数组长度为 5。 2.2 找到字符串中所有字母异位词
题目链接438. 找到字符串中所有字母异位词
题目描述
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。顺序可以不考虑。
异位词是指由相同字母重排列形成的字符串包括相同的字符串。
示例 1
输入s cbaebabacd, p abc输出[0,6]解释 起始索引为 0 的子串是 cba它是 abc 的异位词。 起始索引为 6 的子串是 bac它是 abc 的异位词。
示例 2
输入s abab, p ab输出[0,1,2]解释 起始索引为 0 的子串是 ab它是 ab 的异位词。 起始索引为 1 的子串是 ba它是 ab 的异位词。 起始索引为 2 的子串是 ab它是 ab 的异位词。
提示
1 s.length, p.length 3 * 10^4s 和 p 仅包含小写字母。 解法滑动窗口 哈希表
算法思路 这道题要求我们在字符串 s 中找到所有与字符串 p 的 异位词 对应的子串。由于异位词由相同字母组成且长度与 p 相同因此我们可以使用滑动窗口来解决这一问题。 窗口大小固定 因为异位词的长度一定与字符串 p 的长度相同所以我们构造一个长度为 p.size() 的滑动窗口每次右移窗口动态维护窗口内每个字母的出现频次。 频次匹配判断 通过两个大小为 26 的数组来统计字母出现的次数分别用于存储当前窗口内字母频次hash2和 p 中的字母频次hash1。当两个数组的内容相同说明当前窗口就是 p 的一个异位词。 窗口移动 每次右移窗口时更新窗口内字母的频次。如果窗口超过 p.size()需要将最左边的字母移出窗口。若在滑动过程中两个数组的内容始终保持一致那么我们记录该窗口的起始索引。 算法流程
初始化两个大小为 26 的数组 hash1 和 hash2分别记录 p 中字母的频次和窗口中字母的频次。遍历字符串 s使用右指针 right 逐渐扩大窗口 每次将窗口右端的字母加入窗口并更新其频次。若窗口超过 p.size()则需要从左侧移出一个字母并更新频次。 当 hash1 和 hash2 相等时说明当前窗口是 p 的一个异位词记录其起始位置。 因为直接比较两个哈希表时间复杂度很高这里我们想到了一种优化方式要判断窗口字符串是否是异位词我们只需要判断同一种字符在两个字符串中出现的次数是否一样即可这里我们使用count来统计有效字符的个数即可轻松判断窗口字符串是否是p的异位词最后返回所有满足条件的起始位置列表。 代码实现
#include vector
using namespace std;class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ret;int hash1[26] { 0 }; // 统计字符串 p 中每个字符出现的个数for(auto ch : p) hash1[ch - a]; int hash2[26] { 0 }; // 统计窗口里面的每一个字符出现的个数int m p.size();for(int left 0, right 0, count 0; right s.size(); right) {char in s[right];// 进窗口 维护 countif(hash2[in - a] hash1[in - a]) count;if(right - left 1 m) { // 判断窗口是否需要收缩char out s[left];// 出窗口 维护 countif(hash2[out - a]-- hash1[out - a]) count--;}// 更新结果if(count m) ret.push_back(left);}return ret;}
};这里面count是指有效字符的个数很巧妙的判断滑动窗口里的字符串是否满足条件 复杂度分析
时间复杂度O(n)每个字符最多被左右指针访问两次因此时间复杂度为线性。空间复杂度O(1)只需要常数级别的额外空间用于存储两个固定大小的数组。 图解分析
假设输入为 s cbaebabacd, p abc通过滑动窗口的执行过程如下
滑动窗口执行过程图解
IterationLeftRight窗口内字母频次窗口大小当前窗口字母是否为异位词异位词起始索引100[c]1c否-201[c, b]2cb否-302[c, b, a]3cba是0413[b, a, e]3bae否-524[a, e, b]3aeb否-635[e, b, a]3eba否-746[b, a, d]3bad否-857[a, b, a]3aba否-968[b, a, c]3bac是61079[a, c, d]3acd否- 详细说明 Iteration 1-3Right0 到 Right2窗口内包含 [c, b, a]它与 pabc 完全匹配属于异位词记录起始索引 0。 Iteration 4Right3窗口内包含 [b, a, e]字母 e 不在 p 中因此当前窗口不是异位词。 Iteration 5Right4窗口内包含 [a, e, b]依旧不匹配 p当前窗口不是异位词。 Iteration 6Right5窗口内包含 [e, b, a]仍然不匹配 p当前窗口不是异位词。 Iteration 7Right6窗口内包含 [b, a, d]d 不在 p 中因此当前窗口不是异位词。 Iteration 8Right7窗口内包含 [a, b, a]当前窗口不是异位词。 Iteration 9Right8窗口内包含 [b, a, c]这再次是 pabc 的排列属于异位词记录起始索引 6。 Iteration 10Right9窗口内包含 [a, c, d]d 不在 p 中因此当前窗口不是异位词。 2.3 串联所有单词的子串
题目链接30. 串联所有单词的子串
题目描述
给定一个字符串 s 和一个字符串数组 wordswords 中所有字符串的长度相同。s 中的 串联子串 是指包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如如果 words [ab,cd,ef]那么 abcdef, abefcd, cdabef, cdefab, efabcd 和 efcdab 都是串联子串而 acdbef 不是串联子串因为它不是 words 排列的连接。
返回所有串联子串在 s 中的开始索引顺序可以不考虑。
示例 1
输入s barfoothefoobarman, words [foo,bar]输出[0,9]解释 子串 barfoo 的起始索引为 0它是 words 中按顺序排列的连接。 子串 foobar 的起始索引为 9它是 words 中按顺序排列的连接。
示例 2
输入s wordgoodgoodgoodbestword, words [word,good,best,word]输出[]解释 字符串中没有符合要求的串联子串。
示例 3
输入s barfoofoobarthefoobarman, words [bar,foo,the]输出[6,9,12]解释 子串 foobarthe 的起始索引为 6它是 words 中按顺序排列的连接。 子串 barthefoo 的起始索引为 9子串 thefoobar 的起始索引为 12。
提示
1 s.length 10^41 words.length 50001 words[i].length 30words[i] 和 s 仅包含小写英文字母。 解法滑动窗口哈希表
算法思路 本题可以类比为寻找字符串中所有字母异位词的变种问题。不同的是这里处理的对象是单词而不是单个字符。我们需要遍历字符串 s并通过滑动窗口找到所有符合条件的单词排列。 具体步骤
使用哈希表 hash1 记录 words 中每个单词的频次。遍历字符串 s每次滑动窗口的大小为 words 中单词的总长度。在每个窗口内维护另一个哈希表 hash2用于记录当前窗口内单词的频次。当两个哈希表的内容一致时说明当前窗口是一个符合要求的串联子串记录其起始索引。 同理这里比较两个哈希表是否相等时间复杂度也很高所以我们还是采用优化方式使用count变量来统计有效字符串的个数即可 算法流程
初始化 hash1用于存储 words 中单词的频次。遍历 s通过滑动窗口按单词长度为步长维护窗口内单词的频次。当窗口内的单词频次与 words 中的单词频次一致时记录该窗口的起始索引。 代码实现
#include unordered_map
#include vector
#include string
using namespace std;class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorint ret;unordered_mapstring, int hash1; // 保存 words 中所有单词的频次for (auto word : words) hash1[word];int len words[0].size(), m words.size();for (int i 0; i len; i) { // 执行 len 次unordered_mapstring, int hash2; // 维护窗口内单词的频次for (int left i, right i, count 0; right len s.size(); right len) {string in s.substr(right, len); // 进窗口hash2[in];if (hash1.count(in) hash2[in] hash1[in]) count;// 判断是否需要缩小窗口if (right - left 1 len * m) {string out s.substr(left, len); // 出窗口if (hash1.count(out) hash2[out] hash1[out]) count--;hash2[out]--;left len;}// 更新结果if (count m) ret.push_back(left);}}return ret;}
};复杂度分析
时间复杂度O(n * m * l)其中 n 是字符串 s 的长度m 是 words 中单词的个数l 是单词的长度。每个单词被扫描一次并且最多执行 len 次完整的窗口扫描。空间复杂度O(m * l)用于存储 words 中单词的哈希表以及滑动窗口中的哈希表。 图解分析
滑动窗口执行过程图解
假设输入为 s barfoothefoobarman, words [foo, bar]通过滑动窗口的执行过程如下 具体过程和上一道题类似核心没变操作对象从单个字符变成字符串而已以及一些细节的处理其他都没啥了这里就不详细分析了 IterationLeftRight窗口内单词窗口大小当前窗口单词是否为串联子串串联子串起始索引100[bar]1bar否-203[bar, foo]2barfoo是0369[foo, bar]2foobar是9 详细说明
Iteration 1窗口内的单词为 [bar]不构成完整的串联子串。Iteration 2窗口扩大内含 [bar, foo]它是 words 中单词的排列记录起始索引 0。Iteration 3窗口滑动内含 [foo, bar]它是 words 中单词的排列记录起始索引 9。 2.4 最小覆盖子串
题目链接76. 最小覆盖子串
题目描述
给你一个字符串 s 和一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在这样的子串则返回空字符串 。
注意
对于 t 中重复的字符最小子串中该字符数量必须不少于 t 中的字符数量。如果存在这样的子串答案是唯一的。
示例 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 中只有一个 ‘a’因此不存在符合条件的子串。
提示
1 s.length, t.length 10^4s 和 t 由英文字母组成。 解法滑动窗口 哈希表
算法思路 这是一个典型的滑动窗口问题。目标是找到字符串 s 中能够覆盖 t 所有字符的最小子串。解决思路如下 滑动窗口的应用 我们使用两个哈希表一个用来记录 t 中每个字符的频次另一个用来动态维护滑动窗口中的字符频次。当窗口内的字符满足 t 中每个字符的频次要求时窗口就是一个可行的解。 动态调整窗口大小 通过不断扩大窗口右边界将字符加入窗口。一旦窗口内的字符满足 t 的要求开始缩小窗口左边界尽量缩短窗口长度。 算法流程
初始化两个哈希表hash1 用来记录 t 中每个字符的频次hash2 用来记录窗口内的字符频次。使用滑动窗口右指针 right 不断向右扩展窗口同时更新窗口内的字符频次。每当窗口内的字符频次满足 t 中的要求开始收缩左指针 left缩小窗口并更新最小子串的长度。当遍历结束后返回最小子串的起始索引和长度。
这里面还是需要判断两个哈希表是否相等我们这里还是采用的优化方式使用count变量来统计有效字符不过之前两道题是为了统计字符出现的频次这道题我们统计的是字符出现的种类所以count的和--的情况有所变化喔 代码实现
#include string
#include climits
using namespace std;class Solution {
public:string minWindow(string s, string t) {int hash1[128] { 0 }; // 记录字符串 t 中每个字符的频次int kinds 0; // 统计 t 中不同的字符种类for (auto ch : t) {if (hash1[ch] 0) kinds;}int hash2[128] { 0 }; // 记录窗口中每个字符的频次int minlen INT_MAX, begin -1; // 初始化最小长度和起始位置for (int left 0, right 0, count 0; right s.size(); right) {char in s[right];if (hash2[in] hash1[in]) count; // 进窗口 维护 count// 如果当前窗口满足条件尝试收缩窗口while (count kinds) {if (right - left 1 minlen) { // 更新最小长度和起始位置minlen right - left 1;begin left;}char out s[left]; // 收缩窗口if (hash2[out]-- hash1[out]) count--; // 出窗口 维护 count}}// 返回结果if (begin -1) return ;else return s.substr(begin, minlen);}
};复杂度分析
时间复杂度O(n)其中 n 是字符串 s 的长度滑动窗口遍历每个字符最多两次。空间复杂度O(1)哈希表的大小固定为 128存储字符频次。 图解分析
假设输入为 s ADOBECODEBANC, t ABC滑动窗口的执行过程如下
滑动窗口执行过程图解
IterationLeftRight窗口内字符窗口大小是否为有效窗口最小子串100[A]1否-201[A, D]2否-302[A, D, O]3否-403[A, D, O, B]4否-504[A, D, O, B, E]5否-605[A, D, O, B, E, C]6是ADOBEC716[D, O, B, E, C, O]6否ADOBEC817[D, O, B, E, C, O, D]7否ADOBEC918[D, O, B, E, C, O, D, E]8否ADOBEC1019[D, O, B, E, C, O, D, E, B]9否ADOBEC11110[D, O, B, E, C, O, D, E, B, A]10是ADOBEC12510[C, O, D, E, B, A]6是ADOBEC13610[O, D, E, B, A]5否ADOBEC14611[O, D, E, B, A, N]6否ADOBEC15612[O, D, E, B, A, N, C]7否ADOBEC16912[B, A, N, C]4是BANC 详细说明
Iteration 1-5滑动窗口从 Left0 开始向右扩展但字符尚未覆盖 tABC 的所有字符因此没有有效窗口。Iteration 6Right5 时窗口内字符为 [A, D, O, B, E, C]此时首次找到覆盖 t 的有效窗口记录最小子串为 ADOBEC。Iteration 7-10随着窗口向右扩展字符无法继续满足 t 的要求最小子串保持为 ADOBEC。Iteration 11Right10 时窗口内字符为 [D, O, B, E, C, O, D, E, B, A]再次满足条件最小子串仍保持为 ADOBEC。Iteration 12窗口左移到 Left5依然保持有效窗口字符为 [C, O, D, E, B, A]最小子串保持不变。Iteration 16Right12 时窗口内字符为 [B, A, N, C]再次找到有效窗口更新最小子串为 BANC。 写在最后 在这篇博客中我们继续探索了滑动窗口的高级应用通过对一系列复杂问题的深度剖析进一步展示了滑动窗口的灵活性与高效性。无论是「水果成篮」的双种类约束还是「找到字符串中所有字母异位词」的字符频次比较抑或是「串联所有单词的子串」的字符串匹配与「最小覆盖子串」的字符覆盖问题这些问题都通过滑动窗口的精妙操作得到了优雅的解决。滑动窗口的核心在于对窗口边界的动态调整和哈希表的巧妙使用结合不同场景的需求展现了它在复杂算法挑战中的无限可能性。我们不仅解决了实际问题更深入理解了滑动窗口的算法思想和设计精髓为后续的算法学习打下了坚实基础。 以上就是关于【优选算法篇】踏入算法的深邃乐章滑动窗口的极致探秘的内容啦各位大佬有什么问题欢迎在评论区指正或者私信我也是可以的啦您的支持是我创作的最大动力❤️
