织梦制作手机网站模板免费下载,项目建设目标,网站做用户记录,本地做网站绑定域名文章目录 前言水果成篮思路 找到字符串中所有字母异位词思路 串联所有单词的子串思路 最小覆盖子串思路 总结 前言 本专栏上一篇博客#xff0c;带着大家从认识滑动窗口到慢慢熟悉 相信大家对滑动窗口已经有了大概的认识 其实主要就是抓住——一段连续的区间 今天来学习一些滑… 文章目录 前言水果成篮思路 找到字符串中所有字母异位词思路 串联所有单词的子串思路 最小覆盖子串思路 总结 前言 本专栏上一篇博客带着大家从认识滑动窗口到慢慢熟悉 相信大家对滑动窗口已经有了大概的认识 其实主要就是抓住——一段连续的区间 今天来学习一些滑动窗口进阶的题目 fellow me 水果成篮 思路
一开始看到这个题目一段连续的区间想到了滑动窗口 然后就想着怎么维护窗口每次更新到新的水果种类就要开始对left然后处理数据 其实是有点麻烦的但是经过半个多小时的调试最后还是ac了 思路每次更新两个种类的水果xy如果下一个水果的种类不相符合就更新新的xy 这个时候 right - 1 和 right 所对应的水果就是新的两种然后就是处理从 left 到 right - 1这段区间 符合条件的情况 也就是 从right - 1 一直往前走到与 right - 1 所对应种类不同的水果然后再更新结果 在反复进窗口维护窗口出窗口
代码如下
class Solution
{
public:int totalFruit(vectorint fruits){int ans 0;int n fruits.size();int x fruits[0], y fruits[0];if (n 1)return 1;int left 0, right 1;for (; right n; right){if (fruits[right] ! x fruits[right] ! y) // 和前面确定的水果种类{y fruits[right - 1]; // 更新新的水果种类 x fruits[right];int i right - 1;if (i ! left) // left 到 right - 1 区间 {while (fruits[i] y i left) // i一直靠近left 直到种类不同{i--;}if (i left y ! fruits[left]) // 更新 left 的指向left;else if (i ! left)left i 1;}}ans max(ans, right - left 1);// 更新结果}return ans;}
};后面又想到了一种思路 就是用哈希来统计种类数量哈希相对于前面的那种方法还是简单的 就是把两个种类的水果放入哈希表然后right 水果进窗口如果哈希表的水果种类大于2 就从左侧 left 开始逐步出窗口直到哈希表种类等于2然后更新结果
代码如下
class Solution
{
public:int totalFruit(vectorint f){unordered_mapint, int hash; // 统计窗口内出现了多少种水果int ret 0;for (int left 0, right 0; right f.size(); right){hash[f[right]]; // 进窗口while (hash.size() 2) // 判断{// 出窗口hash[f[left]]--;if (hash[f[left]] 0)hash.erase(f[left]);left;}ret max(ret, right - left 1);}return ret;}
};找到字符串中所有字母异位词 思路
看到又是一段连续的区间就想到了滑动窗口 这一题 p 的异位词说白了就是包含了 p 的所有字母不管先后顺序 想到上一题用哈希优化的爽快这题好像也可以用哈希来解 把 p 中字符都用哈希统计频次然后在遍历 s 时进窗口维护窗口出窗口 每次进入窗口就用哈希统计出现次数只要没有到达次数上限就进窗口 如果进入窗口的字符数量大于了 p 的长度就维护窗口从left开始往右开始出窗口 在每一次统计进入窗口的数量时都比较一下 p 的字符个数如果进入窗口的字符个数等于 p的个数大小相等就更新结果
代码如下
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;}
};下面就上难度了嗷~~~~
串联所有单词的子串 思路
这个题目看起来很难其实一点也不简单看到困难的标签就让人望而生畏 但其实也没有想象的那么难慢慢抽丝剥茧其实也能拿下 看到这里其实就想到了上一题的那个字母异位词本题是说所有单词都包含然后不管顺序 上一题是——所有字母都包含然后不管顺序我们不妨试试上一题的思路呢 首先要解决的就是把单词抽象变成字符我们可以定义一个 string映射 int 的 哈希表这个问题就迎刃而解了 下一个问题就是怎么才能知道哪个是单词的开头字母呢又怎么在 s 中遍历单词然后进窗口呢 我又看到了这个条件雪中送炭所有单词长度相等那岂不是起飞了就让 right 每次遍历 单词长度就好了 这些都处理好了最后一个问题就是我怎么知道哪个字符是单词的第一个字母错乱了怎么办那不是gg 我们只需要在外面套一层for循环从0到单词的长度这段区间都做一次滑动窗口就好啦 核心问题都解决了剩下的就是一些细节处理问题了 话不多说这些都解决了开始执行代码
class Solution
{
public:vectorint findSubstring(string s, vectorstring words) {vectorint ret;unordered_mapstring, int hash1; // 保存 words 里面所有单词的频次for (auto c : words)hash1[c];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) {// 进窗口 维护 countstring in s.substr(right, len);hash2[in];if (hash1.count(in) hash2[in] hash1[in])count;// 判断if (right - left 1 len * m) {// 出窗口 维护 countstring 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;}
};其实hard题也是由一个一个小问题糅合起来的解决核心问题其实也没有那么难 慢慢啃下来还是有成就感的 come on
最小覆盖子串 思路
又又又是一段连续的区间来吧来吧滑动窗口滑动窗口 这道题不是上一题的恰好涵盖所有字符了要返回的是最小子串也就是能包含其他的 但是经过前面题目的磨砺我感觉好像自己有点门道了 思路用哈希1统计字符串 t 的每一个字符的频次还有种类 构造一个新的哈希2然后遍历 s 字符串每个字符都统计到新的哈希表 当这个字符的频次和 哈希1中统计的字符频次相等时种类数 当种类数和哈希1种类数相等时维护窗口更新结果 大致思路就差不多是这样来执行代码吧
class Solution
{
public:string minWindow(string s, string t) {int hash1[128] {0}; // 统计字符串 t 中每一个字符的频次int kinds 0; // 统计有效字符有多少种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; // 进窗口 维护 countwhile (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 ;elsereturn s.substr(begin, minlen);}
};这个困难也拿下啦滑动窗口和哈希一起用感觉有点爽绝佳组合
总结 滑动窗口的核心在于维护一段连续区间通过哈希表优化统计与比较过程。面对不同问题需灵活调整 哈希表记录元素频次快速判断窗口合法性如水果种类、异位词 双指针动态伸缩窗口确保时间复杂度为O(N) 多层循环处理定长元素如单词串联覆盖所有起点情况 种类与频次匹配时更新结果最小子串问题需全局记录最优解 掌握滑动窗口哈希的组合能高效解决子串、子数组等连续区间问题突破Hard瓶颈 今天的内容就到这里啦不要走开小编持续更新中~~~~
