内蒙古网站建站,上海焱灿网络,用啥网站做首页,网络销售平台怎么做前言
滑动窗口一般主要用于解决子数组或子串问题#xff0c;这类的题目更看重对题目的分析和转化。
一、原理
在整个数组上#xff0c;用l和r分别控制窗口的左右边界#xff0c;r就扩大#xff0c;l就减小。
当窗口的范围和题目中某个指标间存在单调关系时#xff0c;…前言
滑动窗口一般主要用于解决子数组或子串问题这类的题目更看重对题目的分析和转化。
一、原理
在整个数组上用l和r分别控制窗口的左右边界r就扩大l就减小。
当窗口的范围和题目中某个指标间存在单调关系时就可以考虑使用滑动窗口解决整个过程一般会需要用某种数据结构或算法来维护信息每次统计的就是子数组以每个位置开头或结尾的答案。
二、题目
1.无重复字符的最长子串
class Solution {
public:int lengthOfLongestSubstring(string s) {mapint,intmp;mapint,int::iterator iter;int ans0;for(int l0,r0;rs.length();r){itermp.find(s[r]);if(iter!mp.end()){lmax(l,mp[s[r]]1);}ansmax(ans,r-l1); mp[s[r]]r;}return ans;}
};
首先分析题目可以发现存在单调性窗口越大越可能出现重复字符。
之后考虑重复这一性质可以用一个哈希map来维护每个字符最晚出现的位置这样当遇到重复的字符直接让l跳到该字符上次出现位置的下一个位置即可。这里注意l只能往前跳
2.长度最小的子数组
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int ansINT_MAX;for(int l0,r0,sum0;rnums.size();r){sumnums[r];while(sum-nums[l]target){sum-nums[l];l;}if(sumtarget){ansmin(ans,r-l1);}}return ansINT_MAX?0:ans;}
};
分析题目单调性窗口越大累加和越大。
于是考虑使用前缀和来维护子数组累加和因为要求长度最小所以若窗口缩小时累加和仍大于target就让窗口缩小。
3.最小覆盖子串
class Solution {
public:string minWindow(string s, string t) {mapint, int cnts;for (int i 0; i t.length(); i) // 统计“欠”{cnts[t[i]]--;}int len INT_MAX;int start 0;for (int l 0, r 0, debts t.length(); r s.length(); r) {if (cnts[s[r]] 0) // 仍然“欠”{debts--; // 需要“还”的减少}if (debts 0) // t中所有字符均满足{while (cnts[s[l]] 0) // 尽量短{cnts[s[l]]--;l;}if (len r - l 1) {len r - l 1;start l;}}}return len INT_MAX ? : s.substr(start, len);//substr第二个参数是取几个}
}; 这个题就非常需要思考了这个思路确实很妙。
先分析单调性窗口越大子串越有可能符合包含t中每个字符的标准。
整体的思路是为了统计子串中是否都包含了t中字符所以可以从“欠”和“还”的角度考虑。
具体来说先统计t中出现的字符将其出现次数设置为“欠”即子串还“欠”这些字符才能满足标准。之后设置debts变量表示一共“欠”的字符个数若新加入的字符是“欠”的状态就让debts减1。当debts等于0时即不再“欠”字符了就开始“还”。具体是只要窗口左侧字符处于“盈余”状态就缩窗口让子串尽量小。为了返回一个串所以每次长度更新时记一下当前窗口左侧位置。
注意substr函数的第二个参数是取几个字符
4.加油站
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int ngas.size();// vectorintrest;// for(int i0;i2;i)// {// for(int j0;jn;j)// {// rest.push_back(gas[j]-cost[j]);// }// }for(int l0,r0,sum;ln;lr1,rl){sum0;//while(sumrest[r]0)while(sumgas[r%n]-cost[r%n]0){ if(r-l1n){return l;} //sumrest[r];sumgas[r%n]-cost[r%n];r;}}return -1;}
}; 这个题的难点在于可以转一圈暴力的做法就是开个两倍长度数组简便方法是取r%n位置的数。
这个题用滑动窗口主要是题目的情景比较符合。
所以依然要用前缀和来维护剩余油量当剩余大于0时就一直往外扩直到长度为n即可以走一圈时返回此时窗口左边界即起始位置。
5.替换子串得到平衡字符串
class Solution {
public:int balancedString(string s) {int ns.length();mapint,intcnts;for(int i0;in;i){cnts[s[i]];}int debts0;for(mapint,int::iterator itercnts.begin();iter!cnts.end();iter){iter-seconditer-secondn/4?0:n/4-iter-second;debts-iter-second;//“欠”}//转化成“找最小覆盖子串”int ansINT_MAX;for(int l0,r0;rn;r){if(cnts[s[r]]0){debts--;}if(debts0){while(cnts[s[l]]0){cnts[s[l]]--;l;}ansmin(ans,r-l1);}}return ans;}
}; 下面几个题就逐渐开始抽象起来了分析难度越来越大更考验对题目的转化。
这个题需要一步转化先统计一遍各个字符的出现次数然后将不够的当作“欠”转化成求这些字符的“最小覆盖子串”。
6.K 个不同整数的子数组
class Solution {
public:int subarraysWithKDistinct(vectorint nums, int k) {//转化 - 小于等于k-小于等于k-1return f(nums,k)-f(nums,k-1);}int f(vectorintnums,int k){mapint,intcnts;int ans0;for(int l0,r0,kinds0;rnums.size();r){if(cnts[nums[r]]1){kinds;}while(kindsk){if(--cnts[nums[l]]0){kinds--;}l;}ansr-l1;//0~3:0~31~32~33~3-四种}return ans;}
}; 首先分析题目会发现等于k其实没有单调性那就考虑将找等于k的个数转化成大于等于k-大于等于k-1的个数。因为窗口越大大于等于k的子数组越长有单调性。
之后就是在统计出现次数时统计种类当种类大于k时让窗口缩小。最后要注意滑动窗口每次统计的是子数组在此范围上以右边界结尾的答案所以种类数即窗口长度。
7.至少有 K 个重复字符的最长子串
class Solution {
public:int longestSubstring(string s, int k) {int ans0;for(int require1;require26;require){mapint,intcnts;for(int l0,r0,kinds0,satisfy0;rs.length();r){cnts[s[r]];if(cnts[s[r]]1){kinds;}if(cnts[s[r]]k){satisfy;}while(kindsrequire){if(cnts[s[l]]1){kinds--;}if(cnts[s[l]]k){satisfy--;}cnts[s[l]]--;l;}if(satisfyrequire){ansmax(ans,r-l1);}}}return ans;}
};
这个题就更困难了转化的这一步太难想了。
首先需要分析出这个题里到底是谁存在单调性分析可知窗口越大时字符种类越多。所以要找的子串即只有1种字符大于等于k只有2种字符大于等于k……只有26种字符大于等于k这些情况的最长子串的最大值。太难想了这个思路
所以枚举二十六个字母每次都维护当前map里的字符种类和满足大于等于k这个条件的种类。当种类比需要的大时让窗口缩小最后当满足的种类等于需要的种类数时统计答案。
总结
滑动窗口的这些题确实很难得多见多想将复杂问题转化成简单问题。
END
