/* 滑动窗口算法框架 */ voidslidingWindow(string s, string t){ unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 0; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; // 右移窗口 right++; // 进行窗口内数据的一系列更新 ...
//滑动窗口 框架 classSolution { public: intmaxConsecutiveAnswers(string answerKey, int k){ int n = answerKey.size(); unordered_map<int, int> window; int left = 0, right = 0; int ans = 0; while(right<n){ char c = answerKey[right]; right++; window[c]++; //窗口缩小 while(window['F']> k && window['T']>k){ char d = answerKey[left]; left++; window[d]--; } ans = max(window['F']+window['T'], ans); } return ans; } };
官方 30ms 10mb
classSolution { public: //ch 假设的最大值字母 intmaxConsecutiveChar(string& answerKey, int k, char ch){ int n = answerKey.length(); int ans = 0; //sum 为另一种 杂质字母的数量 for (int left = 0, right = 0, sum = 0; right < n; right++) { sum += answerKey[right] != ch; while (sum > k) { //不断left++ 减小另一个字母数量 sum -= answerKey[left++] != ch; } ans = max(ans, right - left + 1); } return ans; }
classSolution { public: intlongestOnes(vector<int>& nums, int k){ int n = nums.size(); unordered_map<int,int> window; int left = 0, right = 0; int ans = 0; while(right<n){ int c = nums[right]; window[c]++; right++; while(window[0]>k){ int d = nums[left]; left++; window[d]--; } ans = max(ans, window[1] + window[0]); } return ans; } };
空间优化版本：只需要维护0的个数就可以了
classSolution { public: intlongestOnes(vector<int>& A, int K){ int res = 0, zeros = 0, left = 0; for (int right = 0; right < A.size(); ++right) { if (A[right] == 0) ++zeros; while (zeros > K) { if (A[left++] == 0) --zeros; } res = max(res, right - left + 1); } return res; } };
classSolution { public: intminSubArrayLen(int target, vector<int>& nums){ int left = 0; int right = 0; int n = nums.size(); int sum = 0; int ans = INT_MAX; while(right<n){ sum += nums[right]; right++; while(sum>=target) { ans = min(ans, right - left); sum -= nums[left]; left++; } } return ans == INT_MAX ? 0 : ans; } };
classSolution { public: intnumSubarrayProductLessThanK(vector<int>& nums, int k){ int multi = 1; int n = nums.size(); if(k <= 1) return0; int left = 0, right = 0; int ans = 0; while(right < n){ multi*=nums[right]; while(multi>=k){ multi/=nums[left]; left++; } ans += (right - left + 1); //注意 每次+的是窗口的长度 right++; //这个写在前面也是可以的 只是right - left 不加1 } return ans; } };
回溯（假）
classSolution { public: int ans; //vector<vector<int>> all; //vector<int> path; intnumSubarrayProductLessThanK(vector<int>& nums, int k){ ans = 0; for(int i = 0; i<nums.size(); i++){ backtrack(nums, i, 1, k); } // cout<<all.size()<<endl; // for(int i = 0; i<all.size(); i++){ // for(int j = 0; j<all[i].size(); j++){ // cout<<all[i][j]<<" "; // } // cout<<endl; // } return ans; }
voidbacktrack(vector<int>& nums, int startIndex, int preK, int k){ if(startIndex>=nums.size() || preK>=k) return; preK*=nums[startIndex]; //path.push_back(nums[startIndex]); if(preK<k){ ans++; //all.push_back(path); } backtrack(nums, startIndex+1, preK, k); preK /= nums[startIndex]; //path.pop_back(); } };
classSolution { public: intmaxFrequency(vector<int>& nums, int k){ //先排序， 这样每次窗口最右就是要变成的数 sort(nums.begin(), nums.end()); int n = nums.size(); int left = 0, right = 0, ans = 0; while(right < n){ int numR = nums[right]; while(lastK(nums, left, right, k) < 0){ left++; } ans = max(ans, right - left + 1); right++; } return ans; } //表示填充全部窗口元素到相同值 k剩余多少 intlastK(vector<int>& nums, int left, int right, int k){ int dst = nums[right]; int res = 0; for(int i = left; i<right; i++){ res += (dst - nums[i]); } return k - res; } };
解法 滑窗 直接统计差值
classSolution { public: intmaxFrequency(vector<int>& nums, int k){ //先排序， 这样每次窗口最右就是要变成的数 sort(nums.begin(), nums.end()); int n = nums.size(); int left = 0, right = 1, ans = 1; long sum = 0; while(right < n){ //窗口右移，元素变大后所有元素与最大值 新增的差值 sum += (long)(nums[right] - nums[right-1])*(right - left); while(sum > k){ sum -= nums[right] - nums[left]; left++; } ans = max(ans, right - left + 1); right++; } return ans; } };