1.滑动窗口 固定的模板talus就是,设置l,r,首先r++,当满足超过窗口大小的时候,使用while循环,来进行l++,之道跳出这个while循环,最后,还是r<size
1 2 3 4 5 6 7 8 9 10 11 12 13 14 int left = 0 , right = 0 ;while (right < s.size ()) { window.add (s[right]); right++; while (window needs shrink) { window.remove (s[left]); left++; } }
76最小覆盖字串 这个的窗口大小就是t字符串不同的数量,当相等的时候,就进行比较最大值,然后进行移除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution {public : string minWindow (string s, string t) { unordered_map<char ,int > rec; unordered_map<char ,int > cnt; for (auto c:t){ rec[c]++; } int total=rec.size (); int i=0 ,j=0 ; int u=0 ; string ans=s; bool flag=false ; int start=0 ,len=INT_MAX; while (i<s.size ()){ if (rec.find (s[i])!=rec.end ()){ cnt[s[i]]++; if (cnt[s[i]]==rec[s[i]]){ u++; } } while (u==total){ flag=true ; if (i-j+1 <len){ start=j; len=i-j+1 ; } if (rec.find (s[j])!=rec.end ()){ cnt[s[j]]--; if (cnt[s[j]]<rec[s[j]]){ u--; } } j++; } i++; } if (!flag)return "" ; return s.substr (start,len); } };
这个和上一题差不多,也是
这个思路,然后就是如果长度一样,那么就是直接返回true
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {public : bool checkInclusion (string s1, string s2) unordered_map<char ,int > rec,window; for (auto c:s1)rec[c]++; int l=0 ,r=0 ; int u=0 ; while (l<s2. size ()){ char c=s2[l]; if (rec.count (c)){ window[c]++; if (window[c]==rec[c])u++; } l++; while (u==rec.size ()){ if (l-r==s1. size ())return true ; auto t=s2[r]; if (rec.count (t)){ window[t]--; if (window[t]<rec[t]){ u--; } } r++; } } return false ; } };
求出最大的最长字串,那么这个窗口就是每一个字母出现的次数就是1,超过1,就开始进行滑动窗口
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : int lengthOfLongestSubstring (string s) int l=0 ,r=0 ; int ans=0 ; int u=0 ; unordered_map<char ,int > rec; while (r<s.size ()){ auto c=s[r]; rec[c]++; while (rec[s[r]]>1 ){ auto t=s[l]; rec[t]--; l++; } r++; ans=max (ans,r-l); } return ans; } };
这个就是滑动窗口是0出现的次数，然后如果超过k，就进行更新
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : int longestOnes (vector<int >& nums, int k) int cnt=0 ; int l=0 ,r=0 ; int ans=0 ; while (r<nums.size ()){ auto c=nums[r]; if (c==0 ){ cnt++; } r++; while (cnt>k){ if (nums[l]==0 ){ cnt--; } l++; } ans=max (ans,r-l); } return ans; } };
这个的滑动窗口就是最大值减去最小值是小于k，所以一旦超过就进行更新，使用set可以来得到最大值还有最小值，然后进行计算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution {public : int longestSubarray (vector<int >& nums, int limit) multiset<int > st; int left = 0 , right = 0 ; int res = 0 ; while (right < nums.size ()) { st.insert (nums[right]); while (*st.rbegin () - *st.begin () > limit) { st.erase (st.find (nums[left])); left ++; } res = max (res, right - left + 1 ); right ++; } return res; } int is_ok (vector<int > &nums,int l,int r) if (l==r){ return 0 ; } int t=0 ; for (int i = l; i < r; ++i) { t=max (abs (nums[r]-nums[i]),t); } return max (t, is_ok (nums,l,r-1 )); } };
这个的思路就是计算最左+最右=5，那我们可以计算中间的=整体的-5，然后我们可以使用前缀和，来进行计算，如果等于了，就来计算。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 class Solution {public : int minOperations (vector<int >& nums, int x) int sum= accumulate (nums.begin (),nums.end (),0 ); int target=sum-x; if (target<0 )return -1 ; int l=0 ,r=0 ; int u=0 ; int res=0 ; bool flag= false ; while (r<nums.size ()){ u+=nums[r]; r++; while (u>target){ u-=nums[l]; l++; } if (u==target){ flag= true ; if (r-l>res){ res=r-l; } } } if (!flag)return -1 ; return nums.size ()-res; } };
这个也还是普通的滑动窗口，大小也是这个k来作为窗口
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int minSubArrayLen (int target, vector<int >& nums) int l=0 ,r=0 ; int u=0 ; bool flag=false ; int ans=INT_MAX; while (r<nums.size ()){ u+=nums[r++]; while (u>=target){ flag=true ; ans=min (ans,r-l); u-=nums[l++]; } } if (!flag)return 0 ; return ans; } };
检查是不是有重复的，使用双指针，来进行计算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution {public : bool containsNearbyDuplicate (vector<int >& nums, int k) int l=0 ,r=0 ; unordered_map<int ,int > rec; while (r<nums.size ()){ rec[nums[r]]++; while (rec[nums[r]]==2 ){ if (nums[l]==nums[r]&&r-l<=k){ cout<<r<<" " <<l<<endl; return true ; } rec[nums[l]]--; l++; } r++; } return false ; } };
这是上面一个题目的扩张，有两个值来进行计算，使用set来进行计算。首先找到比当前值num【i】-t大的值，如果没有就跳过，有而且还满足就是true
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) { int l=0,r=0; set<long>st; for (int i = 0; i < nums.size(); i++) { auto lb = st.lower_bound((long)nums[i] - valueDiff); if (lb != st.end() && *lb <= (long)nums[i] + valueDiff) return 1; st.insert(nums[i]); if (i >= indexDiff) st.erase(nums[i - indexDiff]); } return false; } };
选出至少有k个，这个提普通的窗口没有办法处理，使用枚举的方法，我们手动设置窗口，1-26为出现不同的异构字母，然后满足的窗口来进行滑动。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 typedef pair<char,int> PII; class Solution { public: // 思路枚举出现不同的次数，作为窗口，，1-26，就是串口的大小，然后进行计算 //int longestSubstring(string s, int k) { int k; unordered_map<char,int>cnt;//字符的个数 void add(char c ,int& x ,int& y){ if(!cnt[c])x++;//如果当前字符以前没有,不同字符种数++ cnt[c]++; if(cnt[c] == k)y++;//如果加上c之后,刚好满足条件(即字符c的个数不少于k),则满足条件的字符种数++ } void del(char c, int& x , int& y){ if(cnt[c] == k)y--;//如果当前c字符刚好满足条件,则去掉一个后,不再满足条件,则满足条件的字符种数-- cnt[c]--; if(!cnt[c])x--;//如果刚好字符c删没了,则不同字符种数-- } int longestSubstring(string s, int _k) { k=_k; int res = 0; int n = s.size(); if(n < k)return 0; //允许字符的种数 for(int c = 1 ; c <= 26 ; c++){//只允许一个字符,只允许两个字符,... cnt.clear(); //i是遍历在前面的指针,j是遍历在后面的指针,x是当前窗口内不同字符的种数,y是当前窗口内满足条件的字符的种数 for(int i = 0 ,j = 0 , x = 0 , y = 0; i < n ; i ++){//遍历字符串s add(s[i],x,y);//每次先选先把字符加进来,并更新x和y while(x>c)del(s[j++],x,y);//当窗口内遍历到的字符种数超过了当前允许的字符的种数,就删除窗口的末端 if(x == y)res = max(res ,i-j+1); } } return res; } };
这个的思路就是r-l-1-max（字符串)<=k,所以我们的思路就是进行查找最大值字母
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 int characterReplacement (string s, int k) int left = 0 , right = 0 ; int res = 0 ; int Max = -1 ; vector<int > nums (26 ) ; int n = s.size (); while (right < n){ char c = s[right]; nums[c - 'A' ] ++ ; Max = max (Max, nums[c - 'A' ]); while (right - left + 1 - Max > k){ nums[s[left] - 'A' ] --; Max = max (Max, nums[s[left] - 'A' ]); left ++; } res = max (res, right - left + 1 ); right ++; } return res; } };
这个题目的思路还是比较简单，主要的是如何进行求和。当l到r满足小于的，l+1，l+2的一定也满足，那么ans+=r-l+1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : int numSubarrayProductLessThanK (vector<int >& nums, int k) int l=0 ,r=0 ; int u=1 ; int ans=0 ; if (k<=1 )return 0 ; while (r<nums.size ()){ u*=nums[r]; while (u>=k){ u/=nums[l]; l++; } ans+=r-l+1 ; r++; } return ans; } };
