【优选算法】Sliding-Chakra：滑动窗口的算法流（下）
文章目录
- 1.水果成篮
- 2.找到字符串中所有字母异位词
- 3.串联所有单词的子串
- 4.最小覆盖子串
- 希望读者们多多三连支持
- 小编会继续更新
- 你们的鼓励就是我前进的动力！
本篇接上一篇滑动窗口算法，这一篇有些许难度，为了提升自我，请耐心看完后，多敲代码整理思路，相信能够有莫大的收获😼
1.水果成篮
✏️题目描述：
✏️示例：
传送门：水果成篮
题解:
首先解读题意，简单来说就是找到一个区间，其中的果树种类用数字表示，种类不超过两种，题目默认是能找到至少两种水果，所以求在此前提下能找到的最长区间是多少？
💻第一步：
或许该题可以使用暴力解法解决，但明显时间复杂度太高无法通过示例
因此根据前些题目的经验，由于是找区间，而且要统计种类数量，滑动窗口＋哈希表
💻第二步：
具体的窗口滑动如图所示
先让第一个数据录入，即进窗口，判断不断循环，然后right依次向后移并不断往哈希表录入每个位置种类和更新数据，直到哈希表内的键值对大于2，即种类大于2；此时left减去第一个数据，即出窗口，判断不断循环，然后不断向后移直到哈希表里的一个种类数据变为0，对其进行erase操作减少一个种类，再次开始更新数据
💻代码实现:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution
{
public:
int totalFruit(vector<int>& fruits)
{
unordered_map<int, int> hash;
int ret = 0, n = fruits.size();
for (int left = 0, right = 0; right < n; ++right)
{
hash[fruits[right]]++;
while (hash.size() > 2)
{
hash[fruits[left]]--;
if (hash[fruits[left]] == 0)
{
hash.erase(fruits[left]);
}
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};
2.找到字符串中所有字母异位词
✏️题目描述：
✏️示例：
传送门：找到字符串中所有字母异位词
题解:
首先我们要知道什么是异位词？
本题第一难为解读题意，通常读不懂题目时要多结合示例分析，结合示例1和示例2，把p这个字符串放在s这个字符串里比对，不考虑p的顺序，找到所有异位词，返回其起始下标
💻第一步：
先思考如何在代码运行过程中判断其是否为异位词，只判断个数显然是不行的，既要种类相同，又要出现的个数相同，因为哈希表会减慢运行，这里也只有26种字母，所以我们可以给需要找到的字符串创建模拟哈希表hash1，被寻找的字符串创建模拟哈希表hash2，对比两个哈希表的种类及数量就能准确得出是否为异位词
💻第二步：
具体实现的流程图如图所示，与前些写的题有些许不同
先让第一个数据录入，即进窗口，判断不断循环，然后right依次向后移并不断往哈希表中录入，直到left和right之间的长度大于字符串p；此时left减去第一个数据，即出窗口，判断不断循环，然后向后移1位使长度继续维持为字符串p，check然后如果符合要求则更新结果。然后right向前一位，判断，left向前一位，判断更新结果，以此循环
💻细节问题
这里重点在于如何更新结果，一般的思路是遍历hash1和hash2，并对比两个数组，显然此方法是冗余复杂的，接下来将介绍一种方法，通常想不到，因此很有学习价值
先统计字符串p中的字符种类及数量，count表示s中left和right之间的种类数量，在right移动过程中，字符串s的起始种类数量都为0，然后当字符串s的种类数量小于等于字符串p的种类数量时，说明该位置增加的是有效字符，count++
还是滑动窗口的起始操作，如图当right到e时，明显超出了字符串p的大小，left应该在c，移动left到b，然后当字符串s的种类数量小于等于字符串p的种类数量时，说明该位置减少的是有效字符，count--
最后当两个模拟哈希表中的种类数量相等，即count == m
💻代码实现:
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ret;
int hash1[26] = { 0 };
for (auto ch : p)
{
hash1[ch - 'a']++;
}
int hash2[26] = { 0 };
int n = s.size();
int m = p.size();
for (int left = 0, right = 0, count = 0; right < n; ++right)
{
hash2[s[right] - 'a']++;
if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])
{
count++;
}
if (right - left + 1 > m)
{
if (hash2[s[left] - 'a'] <= hash1[s[left] - 'a'])
{
count--;
}
hash2[s[left] - 'a']--;
left++;
}
if (count == m)
{
ret.push_back(left);
}
}
return ret;
}
};
3.串联所有单词的子串
✏️题目描述：
✏️示例：
传送门：串联所有单词的子串
题解:
本题的题意也有些难以理解，但是结合找到字符串中所有字母异位词这题的铺垫，使得这题也不是无从下手
如图所示，把这些字符串看成一个个的字符，是不是就和之前那题是一样的？
💻细节问题
w每个字符串的长度多长，那么left，right就有几种起始情况
当right移动到最后不足字符串w的长度时，会发生越界，所以要写为right + len <= n
💻代码实现:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution
{
public:
vector<int> findSubstring(string s, vector<string>& words)
{
unordered_map<string, int> hash1;
for (auto s : words)
{
hash1[s]++;
}
vector<int> ret;
int len = words[0].size(), m = words.size(), n = s.size();
for (int i = 0; i < len; ++i)
{
unordered_map<string, int> hash2;
for (int left = i, right = i, count = 0; right + len <= n; 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;
}
};
4.最小覆盖子串
✏️题目描述：
✏️示例：
传送门：最小覆盖子串
题解:
本题题意为在字符串s里找到一个含有t的字符串区间，只要该区间内符合t的种类数量即可，无论其他的字符有多少个
💻细节问题
所以本题虽说是困难难度，但是依据前几题的思路铺垫，这道题也能说不在话下了，依旧是模拟哈希表+滑动窗口（因为哈希表太占空间了，影响效率）
注意当是当hash2中的种类数量和hash1中的种类数量一样时才count++
💻代码实现:
#include <iostream>
#include <string>
using namespace std;
class Solution
{
public:
string minWindow(string s, string t)
{
int hash1[128] = { 0 };
int kinds = 0;
for (auto ch : t)
{
if (hash1[ch]++ == 0)
{
kinds++;
}
}
int hash2[128] = { 0 };
int n = s.size(), minlen = INT_MAX, begin = -1;
for (int left = 0, right = 0, count = 0; right < n; ++right)
{
if (++hash2[s[right]] == hash1[s[right]])
{
count++;
}
while (count == kinds)
{
if (right - left + 1 < minlen)
{
minlen = right - left + 1;
begin = left;
}
if (hash2[s[left]]-- == hash1[s[left]])
{
count--;
}
left++;
}
}
if (begin == -1)
{
return "";
}
else
{
return s.substr(begin, minlen);
}
}
};
也是第一次用时击败100%，比官方还优秀的解法😎
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
