C++滑動(dòng)窗口算法習(xí)題的解題思路及示例代碼
一、長(zhǎng)度最小的子數(shù)組
題目鏈接：長(zhǎng)度最小的子數(shù)組
題目描述：
解題思路：
1.暴力枚舉，枚舉任意一個(gè)數(shù)字當(dāng)作起始位置，然后從這個(gè)位置開始尋找一段最短區(qū)間滿足 >= target（注：這方法會(huì)超時(shí),效率低）
2.滑動(dòng)窗口，由于題目要的是一段連續(xù)的區(qū)間，因此我們可以采用滑動(dòng)窗口的辦法。使用兩個(gè)指針left和right同時(shí)指向起始位置，在right小于數(shù)組長(zhǎng)度前提下，不斷向右移動(dòng)進(jìn)行累加操作（進(jìn)窗口）直到它 >= target（判斷條件），記錄該段區(qū)間的長(zhǎng)度（更新結(jié)果），然后將左端元素劃出去（出窗口）同時(shí)并判斷是否滿足條件，如果不滿足，則讓right++ (進(jìn)入下一個(gè)窗口）
代碼實(shí)現(xiàn)：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int ret = INT_MAX,sum = 0;
for(int left = 0,right = 0;right < nums.size();right++)
{
sum += nums[right];
while(sum >= target)
{
//更新結(jié)果
ret = min(ret,right - left + 1);
sum -= nums[left++];
}
}
return ret == INT_MAX ? 0 : ret;
}
};
二、無重復(fù)字符的最長(zhǎng)子串
題目描述：
解題思路：
1.暴力枚舉，從每一個(gè)位置開始向后，看看無重復(fù)字符在什么位置，返回長(zhǎng)度最長(zhǎng)的那個(gè)（注：效率低）
2.滑動(dòng)窗口 + 哈希表，題目要求依舊是一段連續(xù)的區(qū)間，因此可以采用滑動(dòng)窗口的辦法。定義兩個(gè)指針left 和 right，讓右端元素right進(jìn)入窗口（進(jìn)窗口），并用哈希表統(tǒng)計(jì)該字符的頻次，如果該字符 > 1（判斷條件），則從左側(cè)開始滑出窗口（出窗口），直到該字符的頻次為1時(shí)，更新結(jié)果
代碼實(shí)現(xiàn)：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = {0};
int n = s.size();
int ret = 0;
for(int left = 0,right = 0;right < n;right++)
{
hash[s[right]]++;
while(hash[s[right]] > 1)
{
hash[s[left++]]--;
}
ret = max(ret,right - left + 1);
}
return ret;
}
};
三、最大連續(xù)1的個(gè)數(shù) III
題目鏈接：最大連續(xù)1的個(gè)數(shù) III
題目描述：
解題思路：
1.因?yàn)樵擃}的要求依舊是一段連續(xù)的空間，因此我們可以采用滑動(dòng)窗口的方法來解決。
2.我們不要想著如何去翻轉(zhuǎn)，把問題復(fù)雜化。它的核心就是0的個(gè)數(shù)不超過k個(gè)，我們只要解決這一問題即可
3.可以使用一個(gè)變量zero來記錄0的個(gè)數(shù)，用兩個(gè)指針left和right，right指針負(fù)責(zé)進(jìn)窗口，當(dāng)遇到0時(shí)讓zero++，直到當(dāng)zero > k時(shí)（判斷條件），判斷l(xiāng)eft所指元素是否為0進(jìn)行出窗口，最后更新結(jié)果
代碼實(shí)現(xiàn)：
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int len = 0;
for(int left = 0,right= 0,zero = 0;right < n;right++)
{
if(nums[right] == 0)
{
zero++;
}
while(zero > k)
{
if(nums[left++] == 0)
{
zero--;
}
}
len = max(len,right - left + 1);
}
return len;
}
};
四、將x減到0的最小操作數(shù)
題目鏈接：將x減到0的最小操作數(shù)
題目描述：
解題思路：
由于題目要求的是減去數(shù)組左或右兩端連續(xù)的和為x的最短數(shù)組，如果按照題目的要求那我們解決這個(gè)問題就比較棘手，由于我們不知道它是減去左邊的還是減去右邊的，或者連續(xù)減去左邊等情況，因此我們可以將其進(jìn)行轉(zhuǎn)化為數(shù)組內(nèi)一段連續(xù)的和為sum（nums） - x的最長(zhǎng)數(shù)組，使用滑動(dòng)窗口的解法，然后用整個(gè)數(shù)組的大小減去該段最長(zhǎng)數(shù)組的大小，我們就得到了題目要求的最短操作數(shù)了
代碼實(shí)現(xiàn)：
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int sum = 0;
for(auto n : nums)
{
sum += n;
}
int ret = -1;
int target = sum - x;
if(target < 0)
{
return -1;
}
for(int left = 0,right = 0,tmp = 0;right < nums.size();right++)
{
tmp += nums[right];
while(tmp > target)
{
tmp -= nums[left++];
}
if(tmp == target)
{
ret = max(ret,right - left + 1);
}
}
if(ret == -1)
return ret;
else
return nums.size() - ret;
}
};
五、找到字符中所有字母的異位詞
題目鏈接：找到字符中所有字母的異位詞
題目描述：
解題思路：
滑動(dòng)窗口+ 哈希表，由題可知，字符串p的異位詞的長(zhǎng)度?定與字符串p的長(zhǎng)度相同，所以可以在字符串s 中構(gòu)造?個(gè)長(zhǎng)度為字符串p的長(zhǎng)度相同的滑動(dòng)窗口，用哈希表記錄字符串p中字符出現(xiàn)的個(gè)數(shù)，用一個(gè)變量count記錄長(zhǎng)度，不斷進(jìn)窗口，如果大于異位詞的長(zhǎng)度并且出現(xiàn)的字符在字符串p中也有（判斷條件），就出窗口，讓count–，相反就讓count++，如果等于字符串p的長(zhǎng)度就更新結(jié)果
代碼實(shí)現(xiàn)：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int hash1[26] = {0};
int n = s.size();
int m = p.size();
for(auto ch : p)
{
hash1[ch - 'a']++;
}
int hash2[26] = {0};
int count = 0;
for(int left = 0,right = 0;right < n;right++)
{
char in = s[right];
if(++hash2[in - 'a'] <= hash1[in - 'a'])
{
count++;
}
if(right - left + 1 > m)
{ char out = s[left++];
if(hash2[out - 'a']-- <= hash1[out - 'a'])
{
count--;
}
}
if(count == m)
{
ret.push_back(left);
}
}
return ret;
}
};
六、串聯(lián)所有單詞的子串
題目鏈接：串聯(lián)所有單詞的子串
題目描述：
解題思路：
這道題的解法與上道題的異位詞解法類似，無非就是把字母轉(zhuǎn)化為一個(gè)單詞，因此同樣采用哈希 + 滑動(dòng)窗口的解法
代碼實(shí)現(xiàn)：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
unordered_map<string ,int> hash1;
for(auto& e:words)
{
hash1[e]++;
}
int len = words[0].size();
int m = words.size();
for(int i = 0;i < len;i++)
{
unordered_map<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(hash2[in] <= hash1[in])
{
count++;
}
if(right - left + 1 > len * m)
{
string out = s.substr(left,len);
if(hash2[out] <= hash1[out])
{
count--;
}
hash2[out]--;
left += len;
}
if(count == m)
{
ret.push_back(left);
}
}
}
return ret;
總結(jié)
到此這篇關(guān)于C++滑動(dòng)窗口算法習(xí)題的解題思路及示例代碼的文章就介紹到這了,更多相關(guān)C++滑動(dòng)窗口算法習(xí)題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
VC使用TerminateProcess結(jié)束進(jìn)程實(shí)例
這篇文章主要介紹了VC使用TerminateProcess結(jié)束進(jìn)程的方法,實(shí)例演示了TerminateProcess結(jié)束進(jìn)程的具體實(shí)現(xiàn)過程,在進(jìn)行VC應(yīng)用程序開發(fā)時(shí)非常具有實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10
由于hashmap不是c++ stl中標(biāo)準(zhǔn)實(shí)現(xiàn),這樣在跨平臺(tái)使用時(shí)就可能會(huì)出現(xiàn)問題,下面這篇文章主要給大家介紹了關(guān)于C++中hashmap的一些使用建議,需要的朋友可以參考下2023-03-03
QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn)
本文主要介紹了QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
C語言利用鏈表實(shí)現(xiàn)學(xué)生成績(jī)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言如何利用鏈表實(shí)現(xiàn)學(xué)生成績(jī)管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-11-11
C語言計(jì)算連續(xù)無序數(shù)組中缺省數(shù)字方法詳解
這篇文章主要介紹了C語言計(jì)算連續(xù)無序數(shù)組中缺省數(shù)字方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2023-02-02
本篇文章是對(duì)Windows API分解路徑進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++實(shí)現(xiàn)的大數(shù)相乘算法示例
這篇文章主要介紹了C++實(shí)現(xiàn)的大數(shù)相乘算法,結(jié)合實(shí)例形式分析了C++大數(shù)相乘的概念、原理及代碼實(shí)現(xiàn)技巧,需要的朋友可以參考下2017-08-08
詳解C語言如何實(shí)現(xiàn)雙向帶頭循環(huán)鏈表
雙向帶頭循環(huán)鏈表應(yīng)該是鏈表中非常方便的一種，可以很容易的在任意位置上進(jìn)行插入和刪除，可以很容易的對(duì)鏈表進(jìn)行管理。本文將利用C語言實(shí)現(xiàn)雙向帶頭循環(huán)鏈表，需要的可以參考一下2022-08-08
利用Matlab實(shí)現(xiàn)圖像亮度分布統(tǒng)計(jì)圖
這篇文章主要介紹了如何利用Matlab實(shí)現(xiàn)圖像亮度分布統(tǒng)計(jì)圖的繪制，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Matlab有一定的幫助，感興趣的可以了解一下2022-05-05
這篇文章主要為大家詳細(xì)介紹了C++排序算法之插入排序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-08-08