目錄
求最長/最大
2730. 找到最長的半重復子字符串
2779. 數組的最大美麗值
1838. 最高頻元素的頻數
2516. 每種字符至少取 K 個
2831. 找出最長等值子數組
求最短/最小
1234. 替換子串得到平衡字符串
2875. 無限數組的最短子數組
76. 最小覆蓋子串
632. 最小區間
解法一:暴力查找?
解法二:排序+滑窗
解法三:堆
求子數組個數
越長越合法?
2537. 統計好子數組的數目
3298. 統計重新排列后包含另一個字符串的子字符串數目 II
越短越合法
2762. 不間斷子數組
加餐
825. 適齡的朋友
1156. 單字符重復子串的最大長度
424. 替換后的最長重復字符
本篇博客是繼上一篇的續寫,上一篇博客【入門算法】不定長滑動窗口:從動態調整到精準匹配以靈活特性實現高效破題-CSDN博客介紹了不定長滑動窗口的使用場景及方法,以及一些常見的面試題型,本篇博客將對不定長滑動窗口題型進行進一步深入,本章的題目有難度需要有一定的不滑動窗口思想。
PS:本篇博客中的所有題目均來自于靈茶山艾府 - 力扣(LeetCode)分享的題單。
求最長/最大
2730. 找到最長的半重復子字符串
題解:使用滑動窗口,控制窗口內相鄰字符相等的數量最多是1個。
class Solution {
public:int longestSemiRepetitiveSubstring(string s) {//通過滑動窗口來實現int n=s.size();int left=0,count=0; //count記錄窗口中相鄰字符相等的個數int ret=1; for(int right=1;right<n;right++){if(s[right-1]==s[right]) count++; //相鄰字符相等while(count>1) //出窗口 {if(s[left]==s[left+1]) count--;left++; }ret=max(ret,right-left+1); //更新答案}return ret;}
};
2779. 數組的最大美麗值
題解:先對數組進行排序,再使用滑動窗口;通過滑動窗口控制左右兩端之差不超過2*k即可。
class Solution {
public:int maximumBeauty(vector<int>& nums, int k) {//先對數組進行排序//再通過滑動窗口來找最大美麗值int n=nums.size();sort(nums.begin(),nums.end());int left=0,ret=0;for(int right=0;right<n;right++){while(nums[left]+k<nums[right]-k) left++; //此時窗口的最大值和最小值相差太大,進行出窗口ret=max(ret,right-left+1); //更新答案}return ret;}
};
1838. 最高頻元素的頻數
題解:排序+滑動窗口;先對數組進行排序,方便使用最小的k得到最多的頻數。使用滑動窗口控制區間中需要遞增的中次數不超過k。
class Solution {
public:int maxFrequency(vector<int>& nums, int t) {//先對數組進行排序int n=nums.size();sort(nums.begin(),nums.end());int left=0,ret=1;long long k=t;for(int right=1;right<n;right++){//如果當前位置與上一個元素位置不相同,需要將前面所有元素進行遞增if(nums[right]>nums[right-1]) k-=((long long)right-left)*((long long )nums[right]-nums[right-1]);while(k<0) //當遞增的次數大于k,要進行出窗口{if(nums[left]<nums[right]) k+=nums[right]-nums[left];left++;}ret=max(ret,right-left+1); //更新答案}return ret;}
};
2516. 每種字符至少取 K 個
class Solution {
public:int takeCharacters(string s, int k) {int ch[3]={0};for(auto e:s) ch[e-'a']++; //統計字符串中各個字符的總個數for(int i=0;i<3;i++) {ch[i]-=k; //計算刪去左右兩邊后中間區間各個字符最多出現的個數if(ch[i]<0) return -1;}int n=s.size();int left=0,ret=0;for(int right=0;right<n;right++){ch[s[right]-'a']--; //入窗口while(ch[0]<0||ch[1]<0||ch[2]<0) //當中間區間字符出現的次數大于可以出現的次數進行出窗口{ch[s[left]-'a']++; //出窗口left++;}ret=max(ret,right-left+1); //更新答案}return n-ret;}
};
2831. 找出最長等值子數組
題解: 滑動窗口;以滑動窗口的最左側作為窗口中相同的值,控制窗口內不同值的個數少于k即可。
class Solution {
public:int longestEqualSubarray(vector<int>& nums, int k) {int n = nums.size();unordered_map<int, int> count;count[nums[0]]++;int right=1,ret=0;for(int left=0;left<n;left++){//right-left表示窗口長度,count[nums[left]]表示窗口類相同值個數while (right < n && k >= right - left - count[nums[left]]) //保持窗口內不同個數小于k{count[nums[right]]++; //進行入窗口right++;}ret = max(ret, count[nums[left]]); //更新答案count[nums[left]]--; //出窗口}return ret;}
};
求最短/最小
求最短長度/求最小值與最大值類型相同,僅僅是將取最大值修改為取最小值。只不過需要注意更新答案的位置應該在哪。
1234. 替換子串得到平衡字符串
題解:找一個子字符串,對子字符串中字符進行替換實現平衡字符串,找到最短子字符串即可。題目中將這一字符串稱為待替換子串,應該如何找最短待替換字串???待替換字串以外的所有種類字符的個數都滿足小于等于平均值。正難則反,通過關注待替換子串以外的每種字符的個數來確定其是否滿足要求即可。
class Solution {
public:int balancedString(string s) {//題目希望找到一個字符串,該字符串經過替換之后能夠讓字符串s稱為平衡字符串、//若待替換子串意外存在出現此處大于m的就不能實現替換unordered_map<char ,int> mm;for(auto e:s) mm[e]++;int n=s.size(),aver=n/4;if(mm['Q']<=aver&&mm['W']<=aver&&mm['E']<=aver&&mm['R']<=aver) return 0;//進行滑動窗口int left=0,ret=INT_MAX;for(int right=0;right<n;right++){mm[s[right]]--; //入窗口while(mm['Q']<=aver&&mm['W']<=aver&&mm['E']<=aver&&mm['R']<=aver){ret=min(ret,right-left+1); //更新答案mm[s[left++]]++; //出窗口}}return ret;}
};
2875. 無限數組的最短子數組
題解:解法一:使用暴力解法模擬多個數組進行查找,可以通過target來確定至少需要多少個完整數組才有可能達到target,比如數組的總和是sum,模擬有(target/sum+1)+1個數組進行滑動窗口來查找是否又滿足的區間;(target/sum+1)+1是完全足夠包含所有情況的,可以思考一下為什么???
class Solution {
public:int minSizeSubarray(vector<int>& nums, int target) {//通過滑動窗口實現//先判斷最少需要多少個numslong long sum=0,n=nums.size();for(auto e:nums) sum+=e;int num=(target/sum+1)*2;int ret=INT_MAX,left=0;long long tmp=0;for(int right=0;right<n*num;right++){tmp+=nums[right%n];while(tmp>target){tmp-=nums[(left++)%n];}if(tmp==target) ret=min(ret,right-left+1);}return ret==INT_MAX?-1:ret;}
};
此解法簡單,當時最后兩個變態的測試用例是過不了的,超出時間限制。所以一下重點講解方法二。
題解二:通過觀察可以看出,如果target是比sum大的時候必定需要一個或多個完整的數組來實現,所以可以直接通過target/sum得到需要多少個完整的數組,此時再通過target%sum得到還需要多少個余數才能補全。該余數就可以只對兩個數組合并進行滑動窗口看是否能夠不全余數,注意此處需要的是兩個數組進行合并而不是1個,可以思考下為什么???
class Solution {
public:int minSizeSubarray(vector<int>& nums, int target) {//通過滑動窗口實現//先判斷最少需要多少個numslong long sum=0,n=nums.size();for(auto e:nums) sum+=e;int num=target/sum; //得到需要的完整nums個數int more=target%sum; //得到需要部分nums的和int ret=INT_MAX,left=0;int tmp=0;for(int right=0;right<n*2;right++) //進行滑動窗口{tmp+=nums[right%n];while(tmp>more){tmp-=nums[(left++)%n];}if(tmp==more) ret=min(ret,right-left+1);}return ret==INT_MAX?-1:ret+num*n;}
};
76. 最小覆蓋子串
?題解:使用map+滑動窗口對字符進行計數,統計區間內各個種類字符數量是否滿足。此題可能會出現超出內存限制的情況,所以可以適當的降低空間的使用,比如:將map改為使用char[128]的數組替代,或者不是存儲返回值string ret,而是先存儲其區間中的起始位置。
class Solution {
public:string minWindow(string s, string t) {//先通過map統計t總各個字符出現的次數,同時記錄t中字符的種類unordered_map<char ,int> mm;for(auto e:t)mm[e]++;int n=s.size(),left=0,num=mm.size(); //num表示t中的字符種類,同于判斷是否能更新答案int ansl=0,ansr=0,flag=0; //使用flag來標記是否存在適合的字串//進行滑動窗口for(int right=0;right<n;right++){if(mm.count(s[right])){mm[s[right]]--;if(mm[s[right]]==0) num--;}while(num==0){if(ansr==0||ansr-ansl>right-left) {flag=1; //此處采用ansl和ansr的方式來代替string ret//因為后面測試有很長的可能會出現超出內存限制ansl=left,ansr=right; }if(mm.count(s[left])){if(mm[s[left]]==0) num++;mm[s[left]]++;}left++;}}return flag==0?"":s.substr(ansl,ansr-ansl+1);}
};
632. 最小區間
解法一:暴力查找?
解法一:使用滑動窗口,滑動窗口的區間從nums的最小值一直滑到nums的最大值位置。如何判斷區間內的值至少包含數組中的一個元素???使用map對每個數組進行標記,再用一個vector來存儲區間內每個數組的包含量即可。但是此方法毫無疑問會超時。
class Solution {
public:vector<int> smallestRange(vector<vector<int>>& nums) {//使用滑動窗口進行解決,現根據數據確定滑動窗口的最大值和最小值int minum=INT_MAX,maxum=INT_MIN; int k=nums.size();vector<unordered_map<int,int>> v(nums.size()); //統計每個nuums中的數據個數for(int i=0;i<nums.size();i++){if(nums[i].front()<minum) minum=nums[i].front();if(nums[i].back()>maxum) maxum=nums[i].back();for(auto e:nums[i]) v[i][e]++;}vector<int> count(nums.size(),0); //存儲窗口中包含每一個數組的個數int in=0,flag=0; //從最大位置和中最小位置開始進行滑動窗口int left=minum,ansl=minum,ansr=minum;for(int right=minum;right<=maxum;right++){//進行判斷數字是否在k個數組里面for(int i=0;i<k;i++){if(v[i].count(right)) {count[i]++;if(count[i]==1) in++;}}while(in==k){if((ansr==minum&&flag==0)||ansr-ansl>right-left){flag=1; ansr=right,ansl=left; //更新窗口}for(int i=0;i<k;i++){if(v[i].count(left)) {count[i]--; //出窗口if(count[i]==0) in--;}}left++; }}if(flag==0) return {};else return {ansl,ansr};}
};
解法二:排序+滑窗
題解:將K個數組中的元素進行合并,再進行排序。通過滑動窗口來實現在一個區間中每個數組的元素都存在即可。找到區間中最右側-最左側的最小值。
class Solution {
public:vector<int> smallestRange(vector<vector<int>>& nums) {int k=nums.size();vector<pair<int,int>> vv; //pair用于存儲元素的值和對應的數組位置for(int i=0;i<k;i++)for(auto e:nums[i]) vv.push_back({e,i});sort(vv.begin(),vv.end()); //進行排序unordered_map<int,int> count; //存儲每個數組元素出現的次數int ansl=0,ansr=INT_MAX;int n=vv.size(),left=0;for(int right=0;right<n;right++){count[vv[right].second]++; //入窗口while(count.size()==k) {if(ansr-ansl>vv[right].first-vv[left].first)ansr=vv[right].first,ansl=vv[left].first; //更新答案if(--count[vv[left].second]==0) count.erase(vv[left].second);left++;}}return {ansl,ansr};}
};
解法三:堆
題解:使用堆進行實現,從第一個元素開始在K個數組中找最大值max和最小值min,此時的[max,min]就是一個有效的區間,但是不一定是最小區間,所以要進行縮減區間,將min替換成min所在數組的下一個元素來達到縮小區間的目的(也可能不會出現區間縮小的效果,但是并不影響),持續進行直到一個數組走到最后一個位置時停止即可。
細節:使用優先級隊列來實現每次獲取最小值,方便每次刪除最小值及拿去下一個位置元素,此處需要同時存儲元素值,元素所在數組,在該數組位置。所以采用tuple作為基本單元。?
class Solution {
public:vector<int> smallestRange(vector<vector<int>>& nums) {int n=nums.size();int ansl=0,ansr=INT_MAX;//優先級隊列使用tuple作為基本單位,//因為既要存儲最小值,還要存儲所在的數組,以及在數組的對應下標位置priority_queue<tuple<int,int,int> ,vector<tuple<int ,int ,int>> ,greater<>> pq;int themax=INT_MIN; //存儲最大值//進行下標為0的插入for(int i=0;i<n;i++){int tmp=nums[i][0];if(tmp>themax) themax=tmp;pq.push({tmp,i,0});}//進行遍歷while(1){//堆頂就是最小值auto [a,b,c]=pq.top(); //a表示最小值,b表示最小值所在的數組,c表示所在數組對應的下標pq.pop();//更新答案if(ansr-ansl>themax-a) ansl=a,ansr=themax;if(c+1==nums[b].size()) break; //已經沒有元素可以繼續進行插入了,直接停止int next=nums[b][c+1]; //插入下一個元素pq.push({next,b,c+1});themax=max(themax,next); //下一個位置可能是最大值}return {ansl,ansr};}
};
求子數組個數
越長越合法?
2537. 統計好子數組的數目
題解:此處需要進行簡單統計和轉化,當一個數組恰好滿足情況,則向該數組中增加left之前的元素仍然滿足條件,所以仍然可以轉化為越長越合法的模型。
class Solution {
public:long long countGood(vector<int>& nums, int k) {//求臨界區間:有k對滿足情況unordered_map<int,int> mm;int n=nums.size();int left=0,differ=0;long long ret=0;for(int right=0;right<n;right++){differ+=mm[nums[right]]; //統計該元素插入后新的子數組mm[nums[right]]++; //入窗口while(differ>=k){mm[nums[left]]--; //出窗口differ-=mm[nums[left]]; left++;}//此時恰好不滿足ret+=left; //更新答案}return ret;}
};
3298. 統計重新排列后包含另一個字符串的子字符串數目 II
題解:依舊是采用滑動窗口找恰好滿足的情況。?
class Solution {
public:long long validSubstringCount(string word1, string word2) {//仍然是越長越合法的模型,只需要統計word1區間中字符出現的次數即可int ch[128]={0};int count=0; //count用于存儲字符的種類for(auto e:word2) {if(ch[e]==0) count++;ch[e]++;}int n=word1.size();int left=0,k=0; //k用于存儲滿足的字符個數long long ret=0;int hash[128]={0}; //hash用于存儲word1的各個字符個數for(int right=0;right<n;right++){hash[word1[right]]++; //入窗口if(hash[word1[right]]==ch[word1[right]]) k++;while(k==count){if(hash[word1[left]]==ch[word1[left]]) k--; //出窗口hash[word1[left++]]--;}ret+=left; //更新答案}return ret;}
};
越短越合法
2762. 不間斷子數組
題解:根據題目可知區間中最多有3中不同的數;使用map+滑動窗口,使用map是因為map可以直接得到區間中最大值和最小值數據?,將數據與和最大值和最小值進行比較即可。
class Solution {
public:long long continuousSubarrays(vector<int>& nums) {//因為0<=|nums[i1]-nums[i2]|<=2對于數組中每一段都成立,所以區間內最多有3個不同的數map<int ,int> mm; //此處采用map因為我們希望直接拿出來最大值和最小值,//使用unordered_map不能實現,使用map.begin()和map.rbegin()可以實現int n=nums.size(),left=0;long long ret=0;for(int right=0;right<n;right++){mm[nums[right]]++; //入窗口while(mm.rbegin()->first-mm.begin()->first>2) //拿出最大值和最小值進行比較{if(--mm[nums[left]]==0) mm.erase(nums[left]);left++; //出窗口}ret+=right-left+1; //更新答案}return ret;}
};
加餐
825. 適齡的朋友
題解:此題的關鍵在于對題目信息進行轉化,根據題目要求可以得到x要和y發好友請求要滿足:0.5*x+7<y<=x。所以當x越大的時候y就要求越大,而y一直是在x之前的,所以可以先對數組進行排序,再使用滑動窗口控制[left,right],left表示y,right表示x即可。
class Solution {
public:int numFriendRequests(vector<int>& ages) {//由題意知道,發送給y需要滿足的條件是:0.5*x+7<y<=x即可,因為y<=x則第三個條件必定不會成立//x越大y就越大,所以可以使用滑動窗口一個區間中可以發送請求的個數來記錄解決int hash[121]={0}; //使用hash對ages進行排序使得后面的x和y都是線性遞增的for(auto e:ages) hash[e]++;int ret=0,left=0,tmp=0; //使用tmp來記錄[left,right]之間的人數for(int right=0;right<121;right++){tmp+=hash[right]; //入窗口while(2*left<=right+14) //確定滿足0.5*x+7<y時y的位置,tmp-=hash[left++]; //如果不滿足就進行出窗口讓left++,來找更大的yif(left<=right) //判斷y<=x的條件時候滿足ret+=(tmp-1)*hash[right]; //更新窗口}return ret;}
};
1156. 單字符重復子串的最大長度
題解:通過從其他位置交換字符使得形成更大的重復字符串;所以可以先找到一個不同的字符,將字符左右兩邊的重復字符進行統計來得到最長的長度。注意:交換來的字符是否又被區間統計進去。此處建議使用while循環,因為right并不是一直向后走的。
class Solution {
public:int maxRepOpt1(string text) {//此題可以通過交換字符使得相同子串更長unordered_map<char,int> mm; //存儲每一個字符出現的次數for(auto e:text) mm[e]++; int n=text.size();int left=0,ret=0,right=0;while(right<n){while(right<n&&text[left]==text[right]) right++; //求左半邊相同的數int other=right+1; //從other開始進行右半邊的查找while(other<n&&text[left]==text[other]) other++; //求右半邊相同的數ret=max(ret,min(other-left,mm[text[left]])); //min(other-left,mm[text[left]])保證通過其他位置字符進行交換使得連續時,// 交換的位置沒有計數沒有重復left=right; //從不同字符的位置開始進行查找}return ret;}
};
424. 替換后的最長重復字符
題解:通過將區間中不同的字符控制在K以內即可。控制區間[left,right],定義maxcount記錄區間中出現次數最多的重復字符個數,right-left+1-maxcount就是不同的個數。此題的難點在于對于maxcount的修改方面。此處maxcount<=ret<=maxcount+k,此處的ret是答案,因此我們只需要找到maxcount的最大值即可,所以對maxcount的維護只有maxcount=max(maxcount,mm[right])上,當left向右使區間縮小的時候就算是當前區間中maxcount減小了,我們也不需要進行調整,因為maxcount縮小后得到的答案也不會被更新使用;只有在maxcount增大時更新的答案才會被使用。
class Solution {
public:int characterReplacement(string s, int k) {//此題就是找一個最大區間,該區間內不同的字符不能超過k個unordered_map<char ,int> mm; //存儲區間中字符的種類和個數int left=0,n=s.size();int ret=0,right,maxcount=0; //用maxcount來記錄區間中最長重復字符的個數for(int right=0;right<n;right++){mm[s[right]]++;maxcount=max(maxcount,mm[s[right]]); //此處的maxcount只需要在此處進行維護即可while(right-left+1-maxcount>k) //使用right-left-1來表示區間的長度,{ //而right-left+1-maxcount來表示區間中要被替代的個數if(--mm[s[left]]==0) mm.erase(s[left]);left++;}ret=max(ret,right-left+1);}return ret;}
};