滑动窗口习题篇(下)
滑动窗口习题篇(下)
1.水果成篮
题目描述：
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组
fruits表示，其中fruits[i]是第i棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组
fruits，返回你可以收集的水果的 最大 数目。示例 1：
输入：fruits = [1,2,1]
输出：3
解释：
可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：
可以采摘 [1,2,2] 这三棵树。
如果从第⼀棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：
可以采摘 [1,2,1,1,2] 这五棵树。
问题转化：找出一个最长的子数组的长度，子数组中不超过两种类型的水果。
解法一：暴力枚举+哈希表
优化：从前往后进行枚举，即left++时，这时水果的种类不变，right不变；水果的种类变小，right右移。
解法二：滑动窗口
算法思路：
研究的对象是一段连续的区间，可以使用滑动窗口思想来解决问题。
1.进窗口判断条件：
窗口内水果的种类只有两种.
滑动窗口做法：
1.右端水果进入窗口的时候，用哈希表统计这个水果的频次（进窗口）。
2.这个水果进来后，判断哈希表的大小：
- 如果大小超过 2：说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口（出窗口），直到哈希表的大小小于等于 2，然后更新结果；
- 如果没有超过 2，说明当前窗口内水果的种类不超过两种，直接更新结果 ret。
算法流程：
初始化哈希表 hash 来统计窗口内水果的种类和数量；
left = 0，right = 0，记结果变量 ret = 0；
当
right < f.size()，下列一直循环：
将当前水果放入哈希表中（进窗口）；
判断当前水果进来后，哈希表的大小：
- 如果超过 2：（出窗口）
- 将左侧元素滑出窗口，并且在哈希表中将该元素的频次减一；
- 如果这个元素的频次减一之后变成了 0，就把该元素从哈希表中删除；
- 重复上述两个过程，直到哈希表中的大小不超过 2；
更新结果 ret；
right++，让下⼀个元素进入窗口；
- 循环结束后，ret 存的就是最终结果。
代码实现（使用容器）：
class Solution
{
public:
int totalFruit(vector<int>& f)
{
unordered_map<int, 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;
}
};
实现（用数组模拟哈希表）：
class Solution
{
public:
int totalFruit(vector<int>& f)
{
int hash[100001] = { 0 }; // 统计窗⼝内出现了多少种⽔果
int ret = 0;
for(int left = 0, right = 0, kinds = 0; right < f.size(); right++)
{
if(hash[f[right]] == 0) kinds++; // 维护⽔果的种类
hash[f[right]]++; // 进窗⼝
while(kinds > 2) // 判断
{
// 出窗⼝
hash[f[left]]--;
if(hash[f[left]] == 0) kinds--;
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};
2.找到字符串中所有字母异位词
题目描述：
给定两个字符串
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 * 104s和p仅包含小写字母
算法思路：
本题研究对象连续的区间，我们使用滑动窗口思想来解决这道题。
1.如何快速判断两个字符串是否是“异位词”
因为字符串 p 的异位词的长度⼀定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；
当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p的异位词；
因此可以用两个大小为 26 的数组来模拟哈希表。用hash1来保存 p 中每⼀个字符出现的个数，hash2来保存 s 中的子串每个字符出现的个数。这样就能判断两个串是否是异位词。
2.进窗口判断条件：
right-left+1>m(字符串 p 的异位词的长度).
滑动窗口做法：
用
hash1统计字符串 p中每个字符出现的个数，hash2统计窗口里面的每⼀个字符出现的个数；
left=0,right=0，count=0(用来统计窗口中有效字符的个数)；当
right<s.size()，下列一直循环：
如果
right-left+1<=m时,将右端元素划入窗口，当hash2[in]<=hash1[in]时，count++;如果
right-left+1>m时，将左端元素划出窗口，这时要是hash2[out]<=hash1[out]时，count- -;
- 更新结果：当
count==m时，返回ret的值。
代码实现：
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> 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];
// 进窗⼝ + 维护 count
if(++hash2[in - 'a'] <= hash1[in - 'a'])
count++;
if(right - left + 1 > m) // 判断
{
char out = s[left++];
// 出窗⼝ + 维护 count
if(hash2[out - 'a']-- <= hash1[out - 'a'])
count--;
}
// 更新结果
if(count == m)
ret.push_back(left);
}
return ret;
}
};
3.串联所有单词的子串
题目描述：
给定一个字符串
s和一个字符串数组words。words中所有字符串 长度相同。
s中的 串联子串 是指一个包含words中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果
words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。返回所有串联子串在
s中的开始索引。你可以以 任意顺序 返回答案。示例 1：
输入：s = "
barfoothefoobarman", words =["foo","bar"]
输出：[0,9]
解释：因为
words.length == 2同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串"barfoo"开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串"foobar"开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。示例 2：
输入：s = “
wordgoodgoodgoodbestword”,words = ["word","good","best","word"]
输出：[]
解释：因为
words.length == 4并且words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。示例 3：
输入：
s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为
words.length == 3并且words[i].length == 3，所以串联子串的长度必须为 9。
子串"foobarthe"开始位置是 6。它是 words 中以["foo","bar","the"]顺序排列的连接。
子串"barthefoo"开始位置是 9。它是 words 中以["bar","the","foo"]顺序排列的连接。
子串"thefoobar"开始位置是 12。它是 words 中以["the","foo","bar"]顺序排列的连接。提示：
- 1 <=
s.length<= 104- 1 <=
words.length<= 5000- 1 <=
words[i].length<= 30words[i]和s由小写英文字母组成
算法思路：
解法：滑动窗口+哈希表
如果我们把每一个单词看成一个一个字母，问题就变成了上面第二题——找到字符串中所有的字母异位词」。
不同在于之前处理的对象是一个一个的字符，我们这里处理的对象是一个一个的单词。
代码实现：
class Solution
{
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> ret;
unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
for(auto& s : words) hash1[s]++;
int len = words[0].size(), m = words.size();
for(int i = 0; i < len; i++) // 执⾏ len 次
{
unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
for(int left = i, right = i, count = 0; right + len <= s.size(); right += len)
{
// 进窗⼝ + 维护 count
string in = s.substr(right, len);
hash2[in]++;
if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
// 判断
if(right - left + 1 > len * m)
{
// 出窗⼝ + 维护 count
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;
}
};
4.最小覆盖子串
题目描述：
给你一个字符串
s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。- 如果
s中存在这样的子串，我们保证它是唯一的答案。示例 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
解法一：暴力枚举+哈希表
解法二：滑动窗口+哈希表
算法思路：
研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。
1.如何判断当前窗口内的所有字符是符合要求的呢？
我们可以使用两个哈希表，其中⼀个将目标串的信息统计起来，另一个哈希表动态的维护窗口内字符串的信息。
当动态哈希表中包含⽬标串中所有的字符，并且对应的个数都不小于目标串的哈希表中各个字符的个数，那么当前的窗口就是⼀种可行的方案。
算法流程：
1.进窗口判断条件：
hash2中的有效字符大于hash1中的有效字符.
滑动窗口做法：
- 用
hash1用来统计字符串 t 中每⼀个字符的频次,hash2用来统计窗⼝内每个字符的频次;- left=0,right=0,count=0;
- 当
right<s.size()，下列一直循环：
如果
right-left+1<=minlen时,将右端元素划入窗口，当hash2[in]==hash1[in]时，count++;如果
right-left+1>minlen时，将左端元素划出窗口，这时要是hash2[out]==hash1[out]时，count- -;
- 更新结果：起始位置和最短长度
优化：判断条件：
使用变量
count标记有效字符的种类1.进窗口：当
hash2[in]==hash1[in],count++;2.出窗口：当
hash2[out]==hash1[out],count- -;3.判断条件：
count==hash1.size()
代码实现：
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++; // 进窗⼝ + 维护 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);
}
};
最后，本篇文章到此结束，感觉不错的友友们可以一键三连支持一下笔者，有任何问题欢迎在评论区留言哦~