深圳集团网站建设公司,软装设计方案ppt,深圳市造价信息网官网入口,毕业设计做网站滑动窗口大致分为两类#xff1a;一类是窗口长度固定的#xff0c;即left和right可以一起移动#xff1b;另一种是窗口的长度变化#xff08;例如前五道题#xff09;#xff0c;即right疯狂移动#xff0c;left没怎么动#xff0c;这类题需要观察单调性(即指针)等各方… 滑动窗口大致分为两类一类是窗口长度固定的即left和right可以一起移动另一种是窗口的长度变化例如前五道题即right疯狂移动left没怎么动这类题需要观察单调性(即指针)等各方面因素综合思考 长度最小的子数组
长度最小的子数组
题目解析
子数组需要为连续的区间需要在满足条件的前提下长度最短 算法原理
暴力解法暴力枚举出所有子数组的和 枚举子数组左右区间枚举子数组时间复杂度为On2,遍历求和是On。所以时间复杂度是O(n3) 在都为大于0的数的情况下加的数越多和越大所以这里牵扯到了单调性。 先固定一个left左区间用一个sum统计以left为左区间所有数的和即让right开始移动此时相比于暴力解法剩去了一趟遍历此时优化成On2 当right移动到2时sum此时已经大于target,说明已经找到了复合的子数组此时记录长度并让right继续移动继续枚举直至全部枚举完
但随着right向后移动虽然sum可以一直增长满足条件但是len已经在不断增长不符合题意所以right在移动到2的时候就可以停下来了 3. **之后left继续移动到下一个数字3此时我们会让right重新回到3的位置但此时我们发现在left处于2时随着right的移动图示中红框的部分我们其实已经知道了即用当时所求的sum减2即8-26即可这样也剩去了接下来的遍历枚举并且right也不需要回到原来的位置。**br / 优化——利用单调性使用”同向双指针“进行优化同向双指针又叫做滑动窗口 滑动窗口一般是用来维护信息即本题中我们通过[left,right]这个区间维护这个区间的sum。当做题用暴力解法时发现两个指针同向移动不回退时可以用滑动窗口。 初始化窗口先定义两个指针leftright让其充当窗口的左端点右端点 进窗口 初始化完之后right进入窗口sum开始更新为2然后开始做判断 判断是否出窗口 让sum与target作比较如果sumtarget不出窗口先让right移动到合适的位置即使sumtarget。让数字继续进窗口即让3继续进更新sum再与target进行比较。直至right移动到2时sumtarget此时找到了区间更新结果len令len4.更新完之后出窗口即left右移。left移动到3时判断发现sumtarget此时继续进窗口即right右移。如此循环
bc一直循环 更新结果这一步需要结合实际题目具体分析有时候需要进窗口的时候更新结果有的时候需要出窗口时更新结果此题出窗口前更新结果。 滑动窗口的正确性利用单调性规避掉了很多没有必要的枚举 时间复杂度从代码角度看好像是两层循环嵌套时间复杂度似乎也是O(n2)但是实际情况我们对窗口进行操作时left、right每次只移动了一步即我们的两个指针不回退最多两个一共移动nn次即时间复杂度为O(n) 代码实现
class Solution {
public:int minSubArrayLen(int target, vectorint nums){int nnums.size(),sum0,lenINT_MAX;//因为len最终是要取最小值的如果初始化为0会影响。for(int left 0,right 0;rightn;right){sum nums[right]; //进窗口while(sum target) //判断{len min(len,right-left1);sum - nums[left]; //出窗口left;}}return len INT_MAX?0:len; //如果测试用例没有结果就返回0}
};无重复字符的最长字串
无重复字符的最长子串 题目解析
子串和子数组都是连续的一串
算法原理 暴力枚举哈希表判断字符是否重复出现开始遍历使将每个字母都存入哈希表里开始移动并记录长度对比表里是否有重复的字母。时间复杂度On2 优化当left在d位置时开始遍历right移动到a三角形位置时记录长度此时left再移动时跳过与三角形位置相同的字母时再让right开始移动。这样right也不用回退可以省去大量重复且无用的枚举 滑动窗口( 时间复杂度O(n),空间复杂度O(1) ) 初始化窗口定义两个指针充当窗口的两个端点进窗口让字符进入哈希表判断出窗口当窗口内出现重复字符时left移动,当left跳过与right相同字母的位置时将哈希表中与right重复的字母删除将字母频次变为1。 代码实现
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] {0}; //用数组模拟哈希表int left 0,right 0,ns.size();int ret 0;while(rightn){hash[s[right]]; //进入窗口while(hash[s[right]] 1) //判断{hash[s[left]]--; //出窗口,哈希表--然后移动left }ret max(ret,right-left1); //判断right; //让下一个元素进入窗口}return ret;}
};最大连续1的个数
最大连续1的个数
题目解析
题目中翻转指的是可以把0变为1。转化找出最长的子数组0的个数不超过k个
算法原理
暴力枚举zero计数器 固定一个起点向后枚举出所有子数组找出符合条件的子数组即0的个数不超过k比较长度 开始优化——滑动窗口 固定left为第一个位置移动right,当数字是1时忽略1如果是0计数。当zero统计的数字大于k时right不动。移动left当left越过一个0在开始继续移动right 滑动窗口三步走 初始化窗口进窗口向右移动right碰到1无视碰到0计数器1出窗口判断zerok不合法出窗口left移动遇到1无视遇到0计数器-1直至zerok时更新结果 代码实现
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-left1); //更新结果}return ret;}
};将x减到0的最小操作数
将x减到0的最小操作数 题目解析
题目中给的数组所有的元素都是大于1的如果有的数小于等于1单调性不存在是无法使用滑动窗口的每次从数组最左边或者最右边删掉一个数删完之后在新的数组中进行后续操作 算法原理 正难则反正常情况下是在左边选一个区间右边选一个区间让这两个区间的和等于x就可以满足。但是正面作战不利我们可以反过来在中间部分找一个连续的区间使他们和为sum-x也行。(这里的sum是整个数组的和)。题目还要求操作次数最短即找的两边的区间长度需要最短那换言之就是使中间的区间长度最长即可。 暴力枚举固定left和right用sum标记[left,right]所指的这段区域的和判断sum和target之间的关系如果sumtarget,right;直至right移动到使sumtarget的位置right不动开始移动left。 滑动窗口 初始化窗口。进窗口sum±nums[right]。出窗口判断sumtarget, 出窗口sum-nums[left] left; 然后判断出窗口如此循环直至sumtarget更新结果。更新的结果只是子数组的长度len不要忘记n-len才是我们最终想要求的结果。 代码实现
class Solution {
public:int minOperations(vectorint nums, int x) {int sum 0;for(int a:nums) sum a;int target sum-x;//细节问题如果有小于0的元素单调性不存在if(target 0) return -1;int ret -1; //防止有小于0的元素for(int left 0,right 0,temp 0;right nums.size();right) //temp代替sum{tempnums[right]; //进窗口while(temp target ) //判断temp - nums[left]; //出窗口if(temp target)ret max(ret,right-left1); }if(ret -1) return ret;else return nums.size()-ret;}
};水果成篮
水果成篮 题目解析
只能装两种水果可以从任意位置开始但是必须每一棵数上都要采摘所摘的水果需要和当前篮子中的水果一致采摘完之后向右移动如果这棵树和篮子中的水果不一致要立即停止采摘
转化找出一个最长的子数组且子数组中的水果种类不能超过两种
算法原理 暴力枚举哈希表把所有子数组都找出来哈希表统计种类。 固定left开始让right向右移动统计kind当kind大于2的时候让right停下来此时思考right是否需要回退如图所示情况不需要回退right可以随着left后跟着右移。这时可以使用滑动窗口 滑动窗口 初始化窗口left 0right 0进窗口将right所指的元素放进哈希表里hash[fruit[right]]出窗口判断:判断条件hash.length2 left右移,但此时如果我们哈希表里只存储种类的话left移动到哪里才能停下来呢所以哈希表里还要再存储一个数量当这个数字对应的数量为0时把它erase掉。 代码实现
class Solution {
public:int totalFruit(vectorint fruits) {unordered_mapint,inthash; //统计窗口内出现的水果数量int ret 0;for(int left 0,right 0;rightfruits.size();right){hash[fruits[right]]; //进窗口while(hash.size() 2){//出窗口hash[fruits[left]]--; //left位置对应的水果数量--if(hash[fruits[left]] 0)hash.erase(fruits[left]);left; }ret max(ret,right-left1);}return ret;}
};这里因为我们频繁的向哈希表中插入数据所以时间复杂度不是很好。观察题目要求的数据后数据范围有限我们可以用数组模拟哈希表。
class Solution
{public:int totalFruit(vectorint f){int hash[100001] { 0 }; // 统计窗⼝内出现了多少种⽔果int ret 0;for(int left 0, right 0, kinds 0; right f.size(); right) {if(hash[f[right]] 0) kinds; // 维护⽔果的种类hash[f[right]]; // 进窗⼝while(kinds 2) // 判断{// 出窗⼝hash[f[left]]--;if(hash[f[left]] 0) kinds--;left;}ret max(ret, right - left 1);}return ret;}
};找到字符串中所有字母的异位词固定滑动窗口
找到字符串中所有字母的异位词 题目解析 异位词指相同字母重新组合排列产生的新字符串 返回这些子串的起始位置
算法原理
如何快速判断两个字符串是异位词 分别给两个字符串排序检查两个是否相等。但是时间复杂度是Onlognn用哈希表分别遍历记录字符串字母对应位置出现的次数 暴力解法固定不同的位置依次放入哈希表遍历将结果与p进行比较如果相等返回起始位置 滑动窗口我们发现在我们进行第二次开始将子串放入哈希表时中间部分“ba”是一样的只有c和e不同所以我们第二次遍历时只需要将c删掉换成e即可以此类推。即left和right一起移动 初始化窗口left 0right 0进窗口判断出窗口这里判断条件当right右移之后我们的窗口变大了为了保持和p的len一致我们只需要让left移动一步即可这样也就让窗口整体移动了。此时出窗口只需要出一次不需要再和之前的题一样循环判断更新结果仅需判断hash1和hash2是否一样就行。因为窗口小的话是一定不会符合题意的所以这时候不需要更新结果只需要在窗口大小一致的时候检查更新结果即可 这里也可以利用数组模拟哈希表因为题目中说都是小写字母那么我们可以设置一个大小为26的数组在数组为0的位置放a为1的位置放b…让里面存储的值表示出现的次数这样我们在判断hash1和hash2时只需要比较26次。这里的时间复杂度为On 优化更新结果的条件利用count统计窗口里有效字符的个数 进窗口维护当right进入窗口统计第一个字符为c此时记录c的次数为1P中的c也出现了一次当窗口中的c出现次数小于等于P中此时能相互匹配这时c为有效字符令countright移动下一个位置c这时c出现了两次但是P中只出现了一次即不是有效字符count不变right继续往下移动到a…此时count等于3P的长度则此时窗口中全是字母的异位词返回left的位置即可。 出窗口维护当窗口大于P的长度时需要移动left即出窗口删掉字符left移动到第二个c之前我们可以观察此时窗口中c的次数为2大于P中的即为无效字符所以count不需要变化。left移动到第二个c之后c变为一次此时是P的异位词输出起始位置。同理left移动到字符b时此时c仅一次小于等于Pc为有效字符改变count的值为2这时只需要判断count是否等于P的长度就能从而决定我们是否要更新结果。
代码实现
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];// 进窗⼝ 维护 counthash2[in - a];if(hash2[in - a] hash1[in - a]) count;if(right - left 1 m) // 判断{char out s[left];// 出窗⼝ 维护 countif(hash2[out - a] hash1[out - a]) count--;hash2[out - a]--;}// 更新结果if(count m) ret.push_back(left);}return ret;}
};串联所有单词的子串
串联所有单词的子串 题目解析
字符串数组words中所有子串长度相同这点十分重要否则该题时间复杂度很高例如如果 words [“ab”,“cd”,“ef”] 那么 “abcdef” “abefcd”“cdabef” “cdefab”“efabcd” 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串因为他不是任何 words 排列的连接。返回所有串联子串在 s** **中的开始索引。你可以以 任意顺序 返回答案。
算法原理
先将s的字符串按照w中长度的进行划分
hash存储用hashstring,int存储即string存储字符串int存储字符串出现的次数。left与right指针移动移动的步长是单词的长度。滑动窗口执行的次数如图所示紫色、绿色、蓝色 从0、1、2三个位置分别开始划分滑动再往下划分的情况与第一种情况相比只是少了第一个字、符所以结果会重复故一共三次即为len次w的长度。 代码实现
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorintret;unordered_mapstring,int hash1; //保存world单词出现的次数for(autos :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; rightlen s.size();rightlen){//进窗口维护countstring in s.substr(right,len); //将要进窗口的字符串裁出来从right位置开始长度为len的子串hash2[in];if(hash1.count(in) hash2[in] hash1[in]) count;/*这里hash1中不一定有inhash[]的特性是如果没有in会再重新创建一个较消耗时间复杂度。所以可以先加一个判断条件hash1.count(in)*///判断if(right-left1 len*m) //当大于words的总长度时移动窗口{//出窗口维护count string out s.substr(left,len);//这里同理if(hash1.count(out) hash2[out] hash1[out]) count--;hash2[out]--; //出窗口即哈希表里的字符数--leftlen; //left移动}//更新结果if(count m) ret.push_back(left); }}return ret;}
};最小覆盖子串
最小覆盖子串 题目解析
在s中找一个连续的子字符串使其能涵盖t中所有字符即可s中子字符串出现的次数大于t中也可以返回符合条件的子串所以需要标记起始位置 算法原理
暴力解法哈希表枚举出所有符合条件的子串找出最优。 分别在hash1和hash2中统计字符出现的次数在每一次的遍历中比较hash2中出现的次数是否大于等于hash1中出现的次数即可。选一个位置作为起点left然后定义right从left位置开始遍历直到找到符合要求的最短的区间然后right停止此时让left向右移动当left移动前的位置不是题中复合要求的字母时结果没影响right不需要动当left移动前的位置是题中复合要求的字母时此时就不符合要求为了保证符合要求right右移继续找。经分析过后发现right不需要回退left和right都是一起向右移动即滑动窗口。 滑动窗口哈希表 初始化窗口进窗口判断出窗口当hash2中的字符出现次数大于hash1中的字符时即窗口合法时我们出窗口。更新结果这里的更新结果在出窗口之前。因为更新结果我们需要的是符合区间的起始位置和最短长度所以要在出窗口之前获取 优化在判断那里我们比较两个hash出现的字符次数时需要分别遍历两个哈希表是非常消耗时间的并且我们判断还不止一次。 这里的count和之前的不是很一样这里的count记录有效字符的种类。即我们只看出现的A是否成立B是否成立C是否成立而不再统计ABC分别出现的次数因为该题A出现三次大于t中的1次成立出现四次也成立但这里我们只能算作一次在同一段子字符串中可能出现多次见题目解析所以不能再用加和的方式去标记。进窗口维护进窗口之后当两个出现的次数相等时count注意这里不能像之前那样在大于等于的时候让count因为这样会重复统计出窗口维护出窗口之前当此时出现的次数相等时count–A:0-1-0因为出窗口之后没了a有效字符的种类数减少了判断条件我们这里count是统计有效字符的种类所以这里要比较count和hash1的长度t的长度
因为这里都是字符所以我们可以定义数组来模拟hash 代码实现
class Solution {
public:string minWindow(string s, string t) {int hash1[128] {0}; //统计t中出线的频次int kind 0;//统计有效字符种类for(auto ch:t){if(hash1[ch] 0) kind;hash1[ch];} int hash2[128] {0}; //统计窗口内每个字符出现的频次int minlen INT_MAX, begin -1;for(int left 0,right 0,count 0;rights.size();right){char in s[right];hash2[in];if(hash2[in] hash1[in]) count; //进窗口维护while(count kind) //判断条件{if(right-left1 minlen) //更新结果{minlen right - left 1;begin left;}char out s[left];left;if(hash2[out] hash1[out]) count--;hash2[out]--; }}if(begin -1) return ;else return s.substr(begin,minlen);}
};
