C++滑动窗口详解(优选算法)
目录
- 1、长度最小的子数组
- 2、无重复字符的最长字串
- 3.、最大连续 1 的个数 III
- 4、将 x 减到 0 的最小操作数
- 5、水果成篮
- 6、找到字符串中是所有字母异位词(*)
- 7、串联所有单词的字串
- 8、最小覆盖字串
1、长度最小的子数组
思路：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 滑动窗口
// 1.left=0,right=0
// 2.进窗口( += nums[right])
// 3.判断
// 出窗口
// (4.更新结果)
// 总和大于等于 target 的长度最小的 子数组
int n = nums.size();
int l_r_sum = 0;
int ret_len = INT_MAX;
for(int left = 0, right = 0; right < n; right++)
{
// 进窗口
l_r_sum += nums[right];
// 判断
while(l_r_sum >= target)
{
// 更新结果
int len = right - left + 1;
if(len < ret_len)
ret_len = len;
// 出窗口
l_r_sum -= nums[left++];
}
}
return ret_len==INT_MAX?0:ret_len;
}
};
2、无重复字符的最长字串
思路：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 滑动窗口
// 1.left=0,right=0
// 2.进窗口( += nums[right])
// 3.判断
// 出窗口
// (4.更新结果)
int ret_len = 0, n = s.length();
int hash[128] = {0};
int len = 0;
for(int left = 0, right = 0; right < n; right++)
{
// 进窗口
hash[s[right]]++;
// 判断是否含有重复字符
while(hash[s[right]] > 1)
{
// 有重复字符
// 出窗口
hash[s[left]]--;
left++;
len--;
}
// 更新 字串的长度
len++;
if(ret_len < len)
ret_len = len;
}
return ret_len;
}
};
3.、最大连续 1 的个数 III
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
// 滑动窗口
// 1.left=0,right=0
// 2.进窗口( += nums[right])
// 3.判断
// 出窗口
// (4.更新结果)(max:放外面；min:放里面)
// 找出最长的子数组，0的个数不超过K个
int n = nums.size(), ret_count = 0, zero_count = 0;
for(int left = 0, right = 0; right < n; right++)
{
// 进窗口
if(nums[right] == 0)
zero_count++;
// 判断是否超过 k 个
while(left < n && zero_count > k)
{
// 出窗口
if(nums[left++] == 0)
zero_count--;
}
ret_count = max(ret_count, right-left+1);
}
return ret_count;
}
};
4、将 x 减到 0 的最小操作数
思路：
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
// 滑动窗口
// 1.left=0,right=0
// 2.进窗口( += nums[right])
// 3.判断
// 出窗口
// (4.更新结果)(max:放外面；min:放里面)
// 找出最长的子数组，使它们的和等于 sum - x
int all_sum = 0;
for(auto & e : nums)
all_sum+=e;
int target = all_sum-x;
// 1 1 4 2 3
int max_len = -1, n = nums.size();
int max_sum = 0;
for(int left = 0, right = 0; right < n; right++)
{
// 进窗口
max_sum += nums[right];
// 判断
while(left < n && max_sum > target) // 先比它大
{
// 出窗口
max_sum -= nums[left++];
}
if(max_sum == target) // 后判断相等
max_len = max(right-left+1, max_len);
}
return majsx_len==-1?-1:n-max_len;
}
};
5、水果成篮
思路：
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> hash;
int n = fruits.size();
int ret = 0;
for(int left =0,right = 0; right < n; right++)
{
hash[fruits[right]]++;
while(hash.size() > 2) //判断
{
hash[fruits[left]]--;
if(hash[fruits[ljseft]] == 0)
hash.erase(fruits[left]);
left++;
}
ret = max(ret, right-left+1);
}
return ret;
}
};
6、找到字符串中是所有字母异位词(*)
思路：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
// 滑动窗口
// 1.left=0,right=0
// 2.进窗口( += nums[right])
// 3.判断
// 出窗口
// (4.更新结果)(max:放外面；min:放里面)
vector<int> ret_vector;
int hash_s[26] = {0};
int hash_p[26javascript] = {0};
for(auto& xp : p)
hash_p[xp-'a']++;
int n = s.size();
for(int left = 0, right = 0; right < n; right++)
{
// 进窗口
hash_s[s[right]-'a']++;
// 判断两个 hash 是否相同
while(right - left + 1 > p.size())
{
// 出窗口
hash_s[s[left]-'a']--;
left++;
}
if(HashSame(hash_s, hash_p))
// 两个handroidash 相同
ret_vector.push_back(left);
}
return ret_vector;
}
bool HashSame(int* hash_s, int* hash_p)
{
for(int i = 0; i < 26; i++)
{
if(hash_s[i] != hash_p[i])
return false;
}
return true;
}
};
7、串联所有单词的字串
思路：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
unordered_map<std::string, int> hash1;
for (auto& str : words) {
hash1[str]++;
}
int len = words[0].size(), m = words.size();
for (int i = 0; i < len; i++) // 执行 len 次
{
unordered_map<std::string, 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)
{
// 出窗口 + 维护 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;
}
};
8、最小覆盖字串
思路：
class Solution {
public:
string minWindow(string s, string t) {
int hash1[128] = {0};
int kinds = 0; // 统计有效字符有多少种
for(auto& e : t)
{
if(hash1[e] == 0) kinds++;
hash1[e]++;
}
int hash2[128] = {0}; // 维护s
int minlen = INT_MAX, begin = -1;
for(int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
hash2[in]++;
if(hash2[in] == hash1[in]) count++;
while(kinds == count)
{
if(right - left + 1 < minlen)
{
minlen = right - left +1;
begin = left;
}
char out = s[left++];
if(hash2[out] == hash1[out]) count--;
php hash2[out]--;
}
}
if(minlen == INT_MAX) return "";
else return s.substr(begin, minlen);
}
};
到此这篇关于C++滑动窗口的文章就介绍到这了,更多相关C++滑动窗口内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！
加载中,请稍侯......
精彩评论