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