网格系统网站,微信导入wordpress,软件技术属于什么学类,苏州园区建设网站首页滑动窗口 滑动窗口经典例题长度最小的子数组无重复字符的最长子串[最大连续1的个数 III](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)[将 x 减到 0 的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description… 滑动窗口 滑动窗口经典例题长度最小的子数组无重复字符的最长子串[最大连续1的个数 III](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)[将 x 减到 0 的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/)水果成篮找到字符串中所有字母异位词串联所有单词的子串最小覆盖子串 滑动窗口
滑动窗口的本质就是同向双指针而且两个指针都不回退条件满足就可以让右指针右移使元素进入窗口否则右移左指针使一些元素退出滑动窗口直至条件满足由于左右指针都是只向右移动不回退故其时间复杂度为O(n)适用于数组等可以下标随机访问的场景。
经典例题
长度最小的子数组 题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的子数组[numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。 class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left0;int right0;vectorint sums;int ansINT_MAX;while(rightnums.size()) {int tmpsums.size()?sums.back():0;sums.push_back(tmpnums[right]);if(sums.back()target){int lleft;int rsums.size()-1;while(lr){if(anssums.size()){anssums.size();}int mid(lr)/2;if(sums.back()-sums[mid]target){leftmid1;if(ansright-left){ansright-left;}lmid1;if(lr||sums.back()-sums[l]target){break;}}else {rmid-1;if(r0(sums.back()-sums[r]target)(ansright-r)){ansright-r-1;}}}}}if(INT_MAXans){return 0;}return ans;}
};class Solution
{
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size(), sum 0, len INT_MAX;for(int left 0, right 0; right n; right){sum nums[right]; // 进窗⼝while(sum target) // 判断{len min(len, right - left 1); // 更新结果sum - nums[left]; // 出窗⼝}}return len INT_MAX ? 0 : len;}
};无重复字符的最长子串 题目描述给定一个字符串 s 请你找出其中不含有重复字符的 最长子串的长度。 class Solution {
public:int lengthOfLongestSubstring(string s) {int len0;int curLen0;int left0;int right0;vectorint counts(256,0);while(rights.size()){if(1counts[s[right]]){curLenright-left;if(lencurLen){lencurLen;}counts[s[left]]0;}else{counts[s[right]]1;}}curLenright-left;if(lencurLen){lencurLen;}return len;}
};class Solution
{
public:int lengthOfLongestSubstring(string s) {int hash[128] { 0 }; // 使⽤数组来模拟哈希表int left 0, right 0, n s.size();int ret 0;while(right n){hash[s[right]]; // 进⼊窗⼝while(hash[s[right]] 1) // 判断hash[s[left]]--; // 出窗⼝ret max(ret, right - left 1); // 更新结果right; // 让下⼀个元素进⼊窗⼝}return ret;}
};最大连续1的个数 III 题目描述给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个 0 则返回 数组中连续 1 的最大个数 。 class Solution {
public:int longestOnes(vectorint nums, int k) {int len0;int curLen0;int left0;int right0;while(rightnums.size()){if(0nums[right]){if(0k){curLenright-left;if(lencurLen){lencurLen;}while(1nums[left]);if(leftright){k;}else{right;}}else{--k;right;}}else{right;}}curLenright-left;if(lencurLen){lencurLen;}return len;}
};class Solution
{
public:int longestOnes(vectorint nums, int k) {int ret 0;for(int left 0, right 0, zero 0; right nums.size(); right){if(nums[right] 0) zero; // 进窗⼝while(zero k) // 判断if(nums[left] 0) zero--; // 出窗⼝ret max(ret, right - left 1); // 更新结果}return ret;}
};将 x 减到 0 的最小操作数 题目描述给你一个整数数组 nums 和一个整数 x 。每一次操作时你应当移除数组 nums 最左边或最右边的元素然后从 x 中减去该元素的值。请注意需要 修改 数组以供接下来的操作使用。如果可以将 x 恰好 减到 0 返回 最小操作数 否则返回 -1 。 class Solution {
public:int minOperations(vectorint nums, int x) {int lenINT_MAX;int left0;int right0;int sum0;while(leftnums.size()) {if(leftright%nums.size()rightnums.size()){break;}sumnums[right%nums.size()];while(sumxleftnums.size()){sum-nums[left];}if(sumxleftnums.size()){if(0left||right1nums.size()){lenmin(len,right-left1);}sum-nums[left];}right;}return lenINT_MAX?-1:len;}
};class Solution
{
public:int minOperations(vectorint nums, int x) {int sum 0;for(int a : nums) sum a;int target sum - x;// 细节问题if(target 0) return -1;int ret -1;for(int left 0, right 0, tmp 0; right nums.size(); right){tmp nums[right]; // 进窗⼝while(tmp target) // 判断tmp - nums[left]; // 出窗⼝if(tmp target) // 更新结果ret max(ret, right - left 1);}if(ret -1) return ret;else return nums.size() - ret;}
};水果成篮 题目描述你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果 你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。 一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。 给你一个整数数组 fruits 返回你可以收集的水果的 最大 数目。 class Solution {
public:int totalFruit(vectorint fruits) {vectorvectorint backet(2,vectorint(2,0));int maxSum0;int left10;int left20;int cur0;while(curfruits.size()){if(fruits[cur]!fruits[0]){break;}cur;}left1cur-1;left2cur;int rightcur;backet[0][0]fruits[0];backet[0][1]cur;if(curfruits.size()){backet[1][0]fruits[cur];}while(rightfruits.size()){if(fruits[right]backet[0][0]){backet[0][1];left1right;}else if(fruits[right]backet[1][0]){backet[1][1];left2right;}else {if(maxSumbacket[0][1]backet[1][1]){maxSumbacket[0][1]backet[1][1];}if(left1left2){backet[1][1]left2-left1;backet[0][0]fruits[right];backet[0][1]1;left1right;}else{backet[0][1]left1-left2;backet[1][0]fruits[right];backet[1][1]1;left2right;}}right; }if(maxSumbacket[0][1]backet[1][1]){maxSumbacket[0][1]backet[1][1];}return maxSum;}
};class Solution
{
public:int totalFruit(vectorint f) {unordered_mapint, int hash; // 统计窗⼝内出现了多少种⽔果int ret 0;for(int left 0, right 0; right f.size(); right){hash[f[right]]; // 进窗⼝while(hash.size() 2) // 判断{// 出窗⼝hash[f[left]]--;if(hash[f[left]] 0)hash.erase(f[left]);left;}ret max(ret, right - left 1);}return ret;}
};
找到字符串中所有字母异位词 题目描述给定两个字符串 s 和 p找到 s 中所有 p 的 异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。 class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint originCount(128,-1);vectorint curCount(128,0);int count0;int i0;for(;ip.size();i){if(-1originCount[p[i]]){originCount[p[i]]1;}else{originCount[p[i]];}}int left0;int right0;vectorint ans;for(;rights.size();right){if(-1originCount[s[right]]){curCountvectorint(128,0);leftright1;count0;}else{if(curCount[s[right]]originCount[s[right]]){curCount[s[right]];count;}else{for(;leftright;left){if(s[left]s[right]){left;break;}--count;curCount[s[left]]--;}}}if(countp.size()){ans.push_back(left);}}return ans;}
};class Solution
{
public:vectorint findAnagrams(string s, string p) {vectorint ret;int hash1[26] { 0 }; // 统计字符串 p 中每个字符出现的个数for(auto ch : p) hash1[ch - a];int hash2[26] { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数int m p.size();for(int left 0, right 0, count 0; right s.size(); right){char in s[right];// 进窗⼝ 维护 countif(hash2[in - a] hash1[in - a]) count; if(right - left 1 m) // 判断{char out s[left];// 出窗⼝ 维护 countif(hash2[out - a]-- hash1[out - a]) count--; }// 更新结果if(count m) ret.push_back(left);}return ret;}
};串联所有单词的子串 题目描述给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如如果 words [“ab”,“cd”,“ef”] 那么 “abcdef” “abefcd”“cdabef” “cdefab”“efabcd” 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串因为他不是任何 words 排列的连接。 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。 class Solution {
public:vectorint findSubstring(string s, vectorstring words) {unordered_mapstring,int originCount;for(auto e:words){originCount[e];}int start0;vectorint ans;for(;startwords[0].size();start){unordered_mapstring,int curCount;if(startwords[0].size()*words.size()s.size()){break;}int istart;int jstart;int count0;while(true){string tmps.substr(i,words[0].size());if(tmp.size()!words[0].size()){break;}if(originCount.end()originCount.find(tmp)){curCountunordered_mapstring,int();count0;jiwords[0].size();}else{if(curCount[tmp]originCount[tmp]){count;curCount[tmp];}else{while(true){string ts.substr(j,words[0].size());if(ttmp){jwords[0].size();break;}--count;curCount[t]--;jwords[0].size();}}}if(countwords.size()){ans.push_back(j);}iwords[0].size();}}return ans;}
};class Solution
{
public:vectorint findSubstring(string s, vectorstring words) {vectorint ret;unordered_mapstring, int hash1; // 保存 words ⾥⾯所有单词的频次for(auto s : words) hash1[s];int len words[0].size(), m words.size();for(int i 0; i len; i) // 执⾏ len 次{unordered_mapstring, int hash2; // 维护窗⼝内单词的频次for(int left i, right i, count 0; right len s.size(); right len){// 进窗⼝ 维护 countstring in s.substr(right, len);hash2[in];if(hash1.count(in) hash2[in] hash1[in]) count;// 判断if(right - left 1 len * m){// 出窗⼝ 维护 countstring out s.substr(left, len);if(hash1.count(out) hash2[out] hash1[out]) count--;hash2[out]--;left len;}// 更新结果if(count m) ret.push_back(left);}}return ret;}
};最小覆盖子串 题目描述给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。 class Solution {
public:string minWindow(string s, string t) {vectorint originCount(128,-1);vectorint curCount(128,0);int i0;for(;it.size();i){if(-1originCount[t[i]]){originCount[t[i]]1;continue;}originCount[t[i]];}string ans;int left0;int right0;int count0;for(;lefts.size();left){if(-1!originCount[s[left]]){break;}}rightleft;for(;rights.size();right){if(-1originCount[s[right]]){continue;}if(curCount[s[right]]originCount[s[right]]){count;}curCount[s[right]];if(countt.size()){printf(%d %d\n,left,right);while(true){if(-1originCount[s[left]]){left;continue;}else if(curCount[s[left]]originCount[s[left]]){curCount[s[left]]--;left;continue;}break;}if(ans.empty()||ans.size()right-left1){anss.substr(left,right-left1);}}}return ans;}
};class Solution {
public:string minWindow(string s, string t) {int hash1[128] {0}; // 统计字符串 t 中每⼀个字符的频次int kinds 0; // 统计有效字符有多少种for (auto ch : t)if (hash1[ch] 0)kinds;int hash2[128] {0}; // 统计窗⼝内每个字符的频次int minlen INT_MAX, begin -1;for (int left 0, right 0, count 0; right s.size(); right) {char in s[right];if (hash2[in] hash1[in])count; // 进窗⼝ 维护 countwhile (count kinds) // 判断条件{if (right - left 1 minlen) // 更新结果{minlen right - left 1;begin left;}char out s[left];if (hash2[out]-- hash1[out])count--; // 出窗⼝ 维护 count}}if (begin -1)return ;elsereturn s.substr(begin, minlen);}
};
