C++滑動窗口詳解(優(yōu)選算法)
更新時間：2025年06月09日 11:00:57 作者：愛寫代碼的搗蛋鬼
這篇文章主要介紹了C++滑動窗口詳解(優(yōu)選算法),本文通過圖文實例相結合給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧
1、長度最小的子數(shù)組
思路：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 滑動窗口
// 1.left=0,right=0
// 2.進窗口( += nums[right])
// 3.判斷
// 出窗口
// (4.更新結果)
// 總和大于等于 target 的長度最小的 子數(shù)組
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.、最大連續(xù) 1 的個數(shù) III
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
// 滑動窗口
// 1.left=0,right=0
// 2.進窗口( += nums[right])
// 3.判斷
// 出窗口
// (4.更新結果)(max:放外面；min:放里面)
// 找出最長的子數(shù)組，0的個數(shù)不超過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 的最小操作數(shù)
思路：
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
// 滑動窗口
// 1.left=0,right=0
// 2.進窗口( += nums[right])
// 3.判斷
// 出窗口
// (4.更新結果)(max:放外面；min:放里面)
// 找出最長的子數(shù)組，使它們的和等于 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 max_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[left]] == 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[26] = {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))
// 兩個hash 相同
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、串聯(lián)所有單詞的字串
思路：
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++) // 執(zhí)行 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; // 統(tǒng)計有效字符有多少種
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--;
hash2[out]--;
}
}
if(minlen == INT_MAX) return "";
else return s.substr(begin, minlen);
}
};到此這篇關于C++滑動窗口的文章就介紹到這了,更多相關C++滑動窗口內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關文章
C語言中settimeofday函數(shù)和gettimeofday函數(shù)的使用
這篇文章主要介紹了C語言中的settimeofday函數(shù)和gettimeofday函數(shù)的使用,注意settimeofday()函數(shù)只返回0和-1,需要的朋友可以參考下2015-08-08
VC++?2019?"const?char*"類型的實參與"LPCTSTR"
這篇文章主要給大家介紹了關于VC++?2019?"const?char*"類型的實參與"LPCTSTR"類型的形參不兼容的解決方法,文中通過圖文介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2023-03-03
C?語言的基本符號就有?20?多個，每個符號可能同時具有多重含義，而且這些符號之間相互組合又使得?C?語言中的符號變得更加復雜起來2022-08-08
C++??STL?_?Vector使用及模擬實現(xiàn)
這篇文章主要介紹了C++ STL_Vector使用及模擬實現(xiàn)，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
考慮一種情況，當我們有兩個同名的人，Zara，在同一個班里。當我們需要對它們進行區(qū)分我們必須使用一些額外的信息和它們的名字，比如它們生活在不同的區(qū)域或者興趣愛好什么的，在C++程序中也會遇到同樣的情況，所以命名空間就此產(chǎn)生2021-11-11
windows下在vim中搭建c語言開發(fā)環(huán)境的詳細過程
這篇文章主要介紹了windows下在vim中搭建c語言開發(fā)環(huán)境,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-05-05
C++?Boost?StringAlgorithms超詳細講解
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標準庫的后備，是C++標準化進程的開發(fā)引擎之一，是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-11-11
這篇文章主要為大家詳細介紹了MFC對話框?qū)崿F(xiàn)梯形分頁，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-06-06
這篇文章主要介紹了深入解析C++編程中線程池的使用,包括線程池的封裝實現(xiàn)等內(nèi)容,需要的朋友可以參考下2015-11-11
這篇文章主要為大家詳細介紹了opencv2實現(xiàn)10張圖像上下左右拼接融合，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03