网站维护总结,深圳产品设计师,网站建设推广兼职,wp系统网站如何做seo滑动窗口指的是维持左、右边界都不回退的一段范围#xff0c;来求解很多子数组#xff08;串#xff09;的相关问题。
滑动窗口的关键是找到范围和答案指标之间的单调性关系#xff08;类似贪心#xff09;。
滑动过程#xff1a;滑动窗口可以用简单变量或者结构来维护…滑动窗口指的是维持左、右边界都不回退的一段范围来求解很多子数组串的相关问题。
滑动窗口的关键是找到范围和答案指标之间的单调性关系类似贪心。
滑动过程滑动窗口可以用简单变量或者结构来维护信息。
求解大流程求子数组在每个位置开头或结尾情况下的答案开头还是结尾在于个人习惯。
下面通过几个题目加深理解。 题目一
测试链接https://leetcode.cn/problems/minimum-size-subarray-sum/
分析如果判断左右边界不回退是应用滑动窗口的关键。设滑动窗口代表以right为结尾的满足条件的最短子数组。假设存在一个满足条件的最短子数组那么将left回退也就是左移也一定会满足条件而我们是要求最短的子数组所以确定了right的情况下left是不会回退的。然后right继续右移寻找更多情况。直到找到满足条件的子数组再判断left是否需要右移。遍历数组即可找到最短子数组的长度。代码如下。
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int ans 100005;int left 0, right 0;int sum 0;for(;right nums.size();right){sum nums[right];if(sum target){while (sum - nums[left] target){sum - nums[left];}ans ans (right - left 1) ? ans : (right - left 1);}}return ans 100005 ? 0 : ans;}
};
其中将ans初始化为100005是因为nums数组最长为100000只要比这个数大就行。 题目二
测试链接https://leetcode.cn/problems/longest-substring-without-repeating-characters/
分析设滑动窗口为以right为结尾的符合条件的最长子串。可以通过一个数组记录每个符号最晚出现的下标。当right来到一个字符的时候把left置为right最晚出现位置下标加1和left的最大值这时候ans和right-left1取最大值然后更新right处字符最晚出现的下标。遍历数组即可得到最长符合条件的子串长度。代码如下。
class Solution {
public:int lengthOfLongestSubstring(string s) {vectorint position;int ans 0;position.assign(256, -1);for(int left 0, right 0;right s.size();right){left left (position[s[right]] 1) ? left : (position[s[right]] 1);ans ans (right - left 1) ? ans : (right - left 1);position[s[right]] right;}return ans;}
};
其中position存储各字符最晚出现下标初始化为-1方便对一个未出现过的字符更新left值时将left更新为0。 题目三
测试链接https://leetcode.cn/problems/minimum-window-substring/
分析设滑动窗口为以right为结尾的子串。可以通过一个数组记录每个字符串t中的每种字符的需要被覆盖的个数同时用一个变量记录总的需要被覆盖个数。当覆盖个数达到要求时开始调整left。调整后计算ans和right-left1的最小值。遍历数组即可求得符合条件的最小子串的长度。代码如下。
class Solution {
public:string minWindow(string s, string t) {if(s.size() t.size()){return ;}vectorint cnt;int ans 100005;int l;int count -t.size();cnt.assign(256, 0);for(int i 0;i t.size();i){--cnt[t[i]];}for(int left 0, right 0;right s.size();right){if(cnt[s[right]] 0){count;}cnt[s[right]];if(count 0){while (cnt[s[left]] - 1 0){cnt[s[left]]--;}if((right - left 1) ans){ans (right - left 1);l left;}}}return ans 100005 ? : s.substr(l, ans);}
};
其中ans设为100005的原因之前说过cnt数组用来记录每种字符需要被覆盖的次数当大于等于0时代表对此种字符覆盖完毕count是总的用来记录覆盖完成与否。 题目四
测试链接https://leetcode.cn/problems/gas-station/
分析设滑动窗口为以begin为开头的能否走完全程。从begin开始只要总油量小于0begin就前移。直到走下去发现距离等于数组长度就可以返回begin。如果遍历完数组没有返回begin则返回-1。代码如下。
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int length gas.size();for(int begin 0, end 0, soil 0, distance 0; begin length;begin){while (soil 0){if(distance length){return begin;}end (begin distance) % length;soil (gas[end] - cost[end]);}soil - (gas[begin] - cost[begin]);distance--;}return -1;}
}; 题目五
测试链接https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
分析设滑动窗口为以left为开头最少需要多长的自由变换的区间可以符合条件。就是说除了自由变换区间中的字符其他字符不动只变换自由变换区间中的字符就可以使这个字符串满足条件。确定下left和right之后更新ans右移left而right并不需要回退。这是因为如果left到right区间是自由变换区间那么left到right1区间也是自由变换区间。同理如果left到right-1区间不是自由变换区间则left1到right-1区间也不是自由变换区间。所以当left右移时right并不需要回退。代码如下。
class Solution
{
public:int cnt[4] {0};bool ok(int num){for (int i 0; i 4; i){if (cnt[i] num){return false;}}return true;}int get_index(char ch){switch (ch){case Q:return 0;case W:return 1;case E:return 2;case R:return 3;}return -1;}int balancedString(string s){int length s.size();int num (length 2);for (int i 0; i length; i){cnt[get_index(s[i])];}if (cnt[0] num cnt[1] num cnt[2] num cnt[3] num){return 0;}int ans length;for (int left 0, right 0; left length; left){while (!ok(num) right length){--cnt[get_index(s[right])];}if (ok(num)){ans ans (right - left) ? ans : (right - left);}cnt[get_index(s[left])];}return ans;}
};
其中cnt数组是用来记录除滑动窗口外每种字符的个数ok方法判断当前滑动窗口是否可以作为自由变换区间。注意代码中区间为左闭右开即[left, right)。 题目六
测试链接https://leetcode.cn/problems/subarrays-with-k-different-integers/
分析这个题可以将其分解出来我们可以写一个f方法用来计算子数组中小于等于k种整数的子数组个数。而要求题目的解只需要f(k)-f(k-1)即可。而分解出来的f方法则可以分析出单调性使用滑动窗口求解。代码如下。
class Solution {
public:vectorint cnt;int f(int num, vectorint nums){cnt.assign(20001, 0);int ans 0;int count 0;for(int left 0, right 0;right nums.size();right){if(cnt[nums[right]] 0){count;}while (count num){if(--cnt[nums[left]] 0){--count;}}ans (right - left 1);}return ans;}int subarraysWithKDistinct(vectorint nums, int k) {return f(k, nums) - f(k-1, nums);}
};
其中count为种类数。 题目七
测试链接https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
分析此题也是一样的如果直接求解单调性很难分析出来。我们可以将其分解为子串中只能有i种字符每种字符必须出现的次数必须大于等于k。只需将i从1到26遍历一次即可找到符合条件的最大子串长度。代码如下。
class Solution {
public:vectorint cnt;int longestSubstring(string s, int k) {int ans 0;int length s.size();for(int i 1;i 26;i){cnt.assign(26, 0);for(int left 0, right 0, kind 0, match 0;right length;right){if(cnt[s[right] - a] 0){kind;}if(cnt[s[right] - a] k-1){match;}cnt[s[right] - a];while (kind i){--cnt[s[left] - a];if(cnt[s[left] - a] k-1){--match;}if(cnt[s[left] - a] 0){--kind;}left;}if(match i){ans ans (right - left 1) ? ans : (right - left 1);}}}return ans;}
};
其中kind为[left, right]区间字符种类数match为区间中大于等于k的字符种类数。
