送给大家一句话:
充满着欢乐与斗争精神的人们,永远带着欢乐,欢迎雷霆与阳光。 —— 赫胥黎
相信通过前两篇的文章的讲解,大家已经对滑动窗口有了较深的认识,今天我们来挑战一下!!! 来做两道困难级的题目。
家人们!!!上链接!!!30. 串联所有单词的子串
根据题目描述,这道题看起来很是复杂呢!?!? 我们要在一个字符串中寻找包含words的所有单词的子串,并会返回对应的开始位置(开始索引)。看这描述十分类似这道题目 438. 找到字符串中所有字母异位词 ,一个是寻找异位词,一个是寻找"异位单词串"。本质是十分相似的。 来看一个样例:
根据这样例,更容易想象为是如同字母一样。
我们先把每个单词抽象为一个字母(方便我们梳理思路),我们只需要找到一个子串中有所有的“字母”即可。 那么,我们来看最简单的算法:暴力枚举。就是遍历所有的子串,以样例来说:
很明显,无需把right重新移动的到left的位置重新开始,直接继续进行移动就可以。
两个指针移动方向一致
那么我们就按照滑动窗口的解题模版来思考细节:
首先我们要解决的是个一般性问题:s 字符串的长度一定是单词的整数倍吗??? 显然不是! 那么就要进行多次滑动窗口!保证可以遍历到所有可能的子串。那进行几次呢???
可以看出来只需要进行单词个数次的循环即可!!!再多就发生重复了!
这样大致的框架就有了,剩下的就是然后判断单词是否满足条件。 依旧时候使用哈希算法,利用无向图来模拟哈希表(string 映射 int)。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
//预备工作
//哈希表1
unordered_map<string,int> hash1;
for(auto ch : words) hash1[ch] ++; //对words进行处理
// 基本变量
int len = words[0].size(); //单词长度(步长)
int m = words.size();//单词个数
int n = s.size();//字符串长度
//答案
vector<int> ans;
//多次进行滑动窗口
for(int i = 0;i < len;i++)
{
//哈希表2 用来进行比较
unordered_map<string,int> hash2;
//进窗口 注意一次移动的步长 注意结束条件(保证最后一个是完整单词,不然会发生越界)
for(int left = i ,right = i ,count = 0; right + len <= n ; right += len )
{
string in = s.substr(right,len);
//进窗口 维护count++ (有效单词数加一)
if(++hash2[in] <= hash1[in])
{
count++;
}
//判断是否超出长度
if(right - left + 1 > m * len)
{
string out = s.substr(left,len);
//出窗口 维护count
if(hash2[out]-- <= hash1[out]) count--;
left += len;
}
//满足条件 更新结果
if(count == m)
{
ans.push_back(left);
}
}
}
return ans;
}
};
我们提交:过啦!!!!
家人们!!! 上链接!!!76. 最小覆盖子串
根据题目描述,我们需要再字符串中寻找能够覆盖 t 中所有字符的 最短子串,这个“覆盖”是包含 t 中的每个字母,不用管顺序。来看样例:
看了样例,应该就理解了这个“覆盖”:
先来最直接的办法 — 暴力枚举,我们来看暴力算法是如何进行的:
这样就完成了任务,那么如何进行优化呢??? 根据暴力的步骤,我们可以看出来两个指针的移动方向是一致的,所以就可以进行滑动窗口算法了。 那么我们就按照滑动窗口的解题模版来思考细节:
这个判断要怎样进行判断???
肯定是使用哈希算法,但是如何保证对应字母个数必须大于等于 t 中字母个数
呢???
这一步与之前的判断略有不同,因为我们可以多字母,来看代码:
class Solution {
public:
string minWindow(string s, string t) {
//滑动窗口 + 哈希算法
//准备工作
int kinds = 0; //字母种类 方便判断
int hash1[128] = {0}; //哈希表1 因为只有使用数组比较方便
//遍历所有字母 确定个数
for (auto ch : t)
if (hash1[ch]++ == 0) kinds++;
// 长度
int n = s.size();
//哈希表2 用来比较
int hash2[128] = { 0 };
int begin = -1 ,minlen = INT_MAX;
for(int left = 0,right = 0 ,count = 0;right < n;right++)
{
char in = s[right];
//进窗口 维护count (对应字母相等时更新 保证满足条件 有效字母加一)
if(++hash2[in] == hash1[in]) count++;
//判断
while(count == kinds)
{
//更新结果
if(right - left + 1 < minlen)
{
minlen = right - left + 1;
begin = left;
}
char out = s[left];
//出窗口 维护count (相等时出窗口 有效字母减少)
if(hash2[out]-- == hash1[out]) count--;
left++;
}
}
return begin == -1 ? "" : s.substr(begin,minlen);
}
};
提交:过啦!!!!!!
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!