怎么样建网站济南软件公司排名

当前位置： 首页 > news >正文

怎么样建网站,济南软件公司排名,前端开发工作内容,wordpress 添加简码目录 滑动窗口#xff0c;引入#xff1a; 滑动窗口#xff0c;本质#xff1a;就是同向双指针#xff1b; 1.⻓度最⼩的⼦数组#xff08;medium#xff09; 1.解析#xff1a;给我们一个数组nums#xff0c;要我们找出最小子数组的和target#xff0c;首先想到的…目录 滑动窗口引入 滑动窗口本质就是同向双指针 1.⻓度最⼩的⼦数组medium 1.解析给我们一个数组nums要我们找出最小子数组的和target首先想到的就是暴力解法 1暴力 2优化滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串medium 1仍然是暴力解法 2优化 进窗口hash[s[right]]; 出窗口 while(hash[s[right]]1)    hash[s[left]]–; 更新len:   right-left1; 3.最⼤连续1的个数IIImedium 1暴力 2优化 进窗口if(nums[right]0) _k;  出窗口while(_kk)  if(nums[left]0)   _k–; 更新lenlenmax(len,right-left1); 总结 4.将x减到0的最⼩操作数(medium) 解析 1暴力 2优化小demo 进窗口retnums[right] 出窗口while(rettarget) ret-nums[left] 更新len if(rettarget)  lenmax(len,right-left1); 总结 5.⽔果成篮medium 解析 1暴力 2优化 进窗口if (hash[fruits[right]] 0) k; 只要遇到 没遇见种类的水果时k才出窗口while (left n k 2)    if (–hash[fruits[left]] 0) k–; 当这种水果数量变成0了也就说明这种水果不存在了种类k-1更新lenlen max(len, right - left 1); 总结 6.找到字符串中所有字⺟异位词medium 解析 1.暴力 2.小优化 大优化 进窗口if(hash2[s[right]]hash1[s[right]]) count; //分为两步先是hash2[s[right]],然后判断是不是小于等于hash1[s[right]]是就说明是一个有效字符 出窗口 if(right-left1nhash2[s[left]]–hash1[s[left]]) count–; 判断减掉的这个 hash2[s[left]]–,是不是小于等于hash1[s[right]]是就说明是一个有效字符 更新left if(countn) ret.push_back(left); 总结 7.串联所有单词的⼦串hard 解析 1.暴力 2.优化 进窗口string str s.substr(right, len);                //进窗口                hash2[str];                if(hash1.count(str) hash2[str] hash1[str]) count; //记录有效字符串的个数 出窗口if(right - left len m * len)                 {                    string _str s.substr(left, len);                    if(hash1.count(_str) hash2[_str] hash1[_str]) count–;                    hash2[_str]–;                    left len;                } 更新leftif(count m) ret.push_back(left); 总结 8.最⼩覆盖⼦串hard 解析 1.暴力 2.优化 进窗口      if (hash1.count(s[right]) hash2[s[right]] hash1[s[right]]) count; 出窗口 while (lenmcount hash1.size())        {            if (lenmlen right - left 1)            {                len right - left 1;                _left left;            }            if (hash1.count(s[left]) –hash2[s[left]] hash1[s[left]]) count–;            while (left n hash2[s[left]] 0) left;//跳过非种类字符        } 更新lenif(lenn) return ;    return s.substr(_left, len); 滑动窗口引入 顾名思义就是在同向双指针的条件下创建的一个窗口大小让两个指针left 和 right 从左向右移动。 滑动窗口本质就是同向双指针 当两个指针都可以做到不回退都能同向进行的时候就可以采用滑动窗口 怎么用定义left0right0来进窗口right出窗口的时候更新left知道rightn时结束 对于滑动窗口的效率提升是利用数组的单调性就比如要枚举left-right之间数字相加之和target那么sumnums[right] 到某个值后target了就不用继续加后面的值了这样就不用枚举后面所有的情况避免了很多没有必要的枚举 时间复杂度代码可能是两层嵌套循环但是实际上就只是right指针和left指针从左走到右不回头的操作那么就是最大时间复杂度也只是nn次2n 是O(N)级别 1.⻓度最⼩的⼦数组medium 题目的意思就是找出最短子数组的和target 这是最经典的滑动窗口的入门问题了可以现在就动手解决一下如果没明白再看解析。 1.解析给我们一个数组nums要我们找出最小子数组的和target首先想到的就是暴力解法 1暴力 就是从第一个元素开始进行相加遍历后面的每一个元素直到right移动到n-1的位置leftright回头重新开始遍历相加然后遇到和sumtarget的时候就更新len最后返回最短的len但是这种做法想都不用想时间复杂度是O(N^2) 绝对会超时 2优化滑动窗口: 再讲滑动窗口做法前我们要考虑为什么可以采用滑动窗口为什么选择滑动窗口。 任何解法都是在暴力下来做优化有了暴力的解法我们可以看出只要固定left 让right使sum和 target 我们就可以停止right的移动因为right继续后移sum继续加和是没有意义的。所以我们这个时候停止righ的移动那么right要会退吗 答案是不用因为sum已经记录了left 到 right 之间的和我们没有必要让right回退后重新计算之间数字的和而是 sum-nums[left] 然后left这样就又可以保证left移动后并且到right之间的值里面被算出来。 这样我们能够发现left 和 right 两个指针并没有进行回退而是一直向前走我们称这种同向的双指针为 “滑动窗口” 。 所以直到rightn时就结束移动。这样在不满足边界条件的前提下进行跟新len 和 让left。 class Solution { public:int minSubArrayLen(int target, vectorint nums) {int nnums.size();int lenINT_MAX,sum0;for(int left0,right0;rightn;right){//进窗口sumnums[right];//出窗口while(sumtarget){//为什么要先更新len因为如果进来的条件是sumtarget 那么就是要先更新最小值最后在leftlenmin(len,right-left1);sum-nums[left];}}return lenINT_MAX?0:len;} }; 通过上面就已经可以分析出“滑动窗口”系列就是 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串medium 如果是按照leetcode顺序刷的话有多少人都死在了这题上面其实如果了解了“双指针”-滑动窗口的过度能很简单解决这题 解析 1仍然是暴力解法 不含有重复字符那么就考虑到从第一个元素开始遍历存到一个字符串str里如果遇到了重复字符就回退right让left在从头开始遍历当然这样的O(N^2) 绝对会超时 2优化 有暴力延伸出双指针定义left 和 right 那么开始遍历的时候right直到遇到重复的字符的时候我们就让left直到跳过  跟s[right] 重复的同一个字符 这时就可以写出定义一个hash表来记录每个字符出现的次数2 就说明重复 进窗口hash[s[right]]; 出窗口 while(hash[s[right]]1)    hash[s[left]]–; 更新len:   right-left1; class Solution { public:int lengthOfLongestSubstring(string s) {if(s.size()1) return 1;unordered_mapchar,int hash;int ns.size();int len0;for(int left0,right0;rightn;right){//进窗口hash[s[right]];//出窗口while(hash[s[right]]1)hash[s[left]]–;lenmax(len,right-left1);}return len;} }; 总结滑动窗口题目模板都大差不差这题因为是考虑去掉重复字符那么可以在每次循环结束都来判断最大的len也不用在while里判断因为可能回造成s字符串没有重复的字符那么就进不去while 3.最⼤连续1的个数IIImedium 只要不对数组直接进行调整移动什么的其实都是比较简单的~ 因为下标都是固定的 解析 1暴力 我在这题也卡了很久暴力无非就是从第一个元素开始遇到1right遇到0k–直到k0然后更新lenright - left 1然后leftright回头 重新遍历重新跟新left那么绝对超时O(N^2); 2优化 通过暴力看也看出每次right走到k0 的时候都要回头重新遍历那么这么多次重新遍历都是无效的我们只需要用len记录后left直到越过一个0k1说明right就又可以往后移动到一个为0 的位置当遇到第二个0的时候right停下来我们就再次更新len就可以得到最长的len 这里要说明的是我们可以定义一个_k ,来记录遇到0的个数当_kk 的时候right仍然可以向后移动这点一定要想清楚只要当_k0 那么边界条件被打破这个时候就要left当nums[left]0 的话移动过去后_k–; 仍然是 进窗口if(nums[right]0) _k;  出窗口while(_kk)  if(nums[left]0)   _k–; 更新lenlenmax(len,right-left1); class Solution { public:int longestOnes(vectorint nums, int k) {int len0;for(int left0,right0,_k0;rightnums.size();right){if(nums[right]0) _k;while(_kk) if(nums[left]0) _k–;lenmax(len,right-left1);}return len;} }; 总结 滑动窗口要从暴力推导到优化还是比较好想的滑动窗口是保证两个指针left跟right依次往前运动不后退保证了效率的提升不用产生无用的操作。 这题就是1.先要保证进窗口//进窗口一定要在前面             if(nums[right]0) _k; 这个就是进窗口的条件当nums[right]0  _k; 2.那么现在考虑出窗口while(_kk) 在这个循环条件里面进行出窗口其实仔细一些如果在_kk 时出窗口是不完美的你还要保证nums[right1]这个时候也是等于0 的。所以条件过于复杂苛刻不便于实现那么在while里面进行出窗口实际上就是让left 只是多加了一个if在满足nums[left]0 的条件下就_k– 来实现出窗口这样就又可以让right继续往后移动 4.将x减到0的最⼩操作数(medium) 这里面藏着一个小demo 如果想不上去这题简直无脑到直逼困难题没有人会一直写代码列举所有左右的情况然后去相减吧题目的意思就有点牵着别人走了。 解析 1暴力 暴力属实无脑开始先减减左边然后减减右边可以用dfs回溯来解决但是压栈太多题目数据大肯定会爆直到x被减为0那么就返回被更新的次数如果只是单纯的这么写那简直不敢想代码量。 2优化小demo 我们可以看出要用最小的操作来求出两边之和为x 那么逆向过来是不是就是用最大的操作次数 求出的和sum-x 那么翻译过来后就明白了是在数组里面找出最大操作次数的和sum - x 那么我们就令 target sum - x 那么这题就跟第一题一样了。 仍然是 进窗口retnums[right] 出窗口while(rettarget) ret-nums[left] 更新len if(rettarget)  lenmax(len,right-left1); class Solution { public:int minOperations(vectorint nums, int x) {int sum0;for(auto e : nums) sume;sum-x;if(sum0) return -1;int len-1,ret0;for(int left0,right0;rightnums.size();right){//进窗口retnums[right];//出窗口while(retsum) ret-nums[left];//更新lenif(retsum) lenmax(len,right-left1);}return len-1?-1:nums.size()-len;} }; 总结 1.这题有很多关键点如果只是按照题目要求来进行描写x减一个左数或减一个右数实在是过于麻烦和复杂时间复杂度绝对超时那么就要逆向思维 2.我们要求最短的操作数那么就是在左右两个位置各找一堆数字的和正好是等于x的加入所有数字和是sum那么反过来的意思就是在这左右两堆数字中间的这堆数 之和正好是 sum - x 且要求他的长度是最长的那么这个意思就立马变简单了那么我们就可以采用滑动窗口从最左边开始查找一直找到最长串的数组和为sum - x 就能达到最好的目的那么最后返回值就是nums.size()-len 3.细节问题sum - x可能0 那么就直接返回 -1 retnums[right] 不用在乎ret sum 的情况因为while里面一定会进行解决retsum 的问题  最后就是ret sum 要单独拿出来进行更新len值 5.⽔果成篮medium 这题相对来说还是比较简单的有了上面几题的经验之后这题只需要记录水果的种类个数不超过2就可以一直装水果然后记录最长子数组个数。 题目意思就是最多只能装两个不同种类的水果求最大子数组的长度。 解析 1暴力 那么就设置两个指针left和right从头开始遍历设置一个计数器k直到right遍历到第三个种类的水果时停止这个时候跟新len 的长度在让leftright回头重新进行遍历那么绝对会超时O(N^2); 2优化 就是设置left和right 从头开始遍历当right遍历到第三个种类的时候就不用回退只需要left直接跳过一个种类的水果的时候这个right就可以进行往前移动然后重复上面的操作就不停的更新len就可以得到最大长度的len 仍然是 进窗口if (hash[fruits[right]] 0) k; 只要遇到 没遇见种类的水果时k才 出窗口while (left n k 2)    if (–hash[fruits[left]] 0) k–; 当这种水果数量变成0了也就说明这种水果不存在了种类k-1 更新lenlen max(len, right - left 1); class Solution { public:int totalFruit(vectorint fruits) {int len 0;int n fruits.size(), k 0;unordered_mapint,int hash;for (int left 0, right 0, tmp 0; right n; right){//进窗口if (hash[fruits[right]] 0) k;//出窗口while (left n k 2)if (–hash[fruits[left]] 0) k–;//更新lenlen max(len, right - left 1);}return len; } }; 总结 滑动窗口这一题就是在hash里面最多只能存放两种水果 1.暴力那么就是从第一个开始依次加入水果直到超过三个就开始计算长度left right在从头开始计算想都不要想这样的暴力绝对超时 2.优化滑动窗口因为考虑到right走到第三种水果的时候left就开始只需要减去最开始left 的这个水果那么要设置一个计数器k因为在最开始我一直以为hash减到0了hash.size() 就会变小但其实不会任然存在并且也可以变成负数所以要采用计数器kif (hash[fruits[right]] 0) k; 存在新水果k if (–hash[fruits[left]] 0) k–; 超过水果个数k那么就只要最开始left水果变成0k就–这样right就可以继续移动 最后一直更新len的值就行 6.找到字符串中所有字⺟异位词medium 题目意思就是在s里找pp的顺序是任意的但是要包含所有字符返回s里面所有满足条件的字符下标。没有思路的话可以先试试暴力枚举 解析 1.暴力 暴力枚举其实也有难度比如要先讲p排序不然要列举出p的各种顺序肯太复杂对比不过来然后设置strs[right]长度lenright-left1      p.size(); 然后对str进行排序在判断strp? 如果等于就存入str的下标否则就跳过left和right都 2.小优化 用两个hash表来比较纯如的字符是否完全相等如果是就加入left但是这样会有一个用例超时说明还可以继续优化。 class Solution { public:vectorint findAnagrams(string s, string p) {int ns.size(),mp.size();unordered_mapchar,int hash1;for(auto e : p) hash1[e];unordered_mapchar,int hash2;vectorint v;for(int left0,right0;rightn;right){hash2[s[right]];while(right-left1m) hash2[s[left]]–;//判断两个字符数组是否相等if(hash1.count(s[right])){int f0;for(int i0;im;i){if(hash2[p[i]]!hash1[p[i]]){f1;break;}}if(f0) v.push_back(left);}}return v;} }; 大优化 其实对于暴力解要排序strp 时间复杂度都是很高的代价并且每个字串str都要进行判断真的太无效了比如明知道str“bae” pabc,明知道二者不可能相等还非要去比较那这样显得太呆了所有我们就要设置一个计数器count 来记录在这个固定的滑动窗口里面 有多少个有效的字符。 因为前面题目都是不固定长的窗口大小这里是固定长的窗口大小所以我们出窗口的条件就跟前面题目不一样这里只需要countp.size() 就说明有效字符已经达到加入left就ok然后就可以进行出窗口。 所以还是比较简单的复杂一点的位置和细节就是要判断有效字符的个数count 进窗口if(hash2[s[right]]hash1[s[right]]) count; //分为两步先是hash2[s[right]],然后判断是不是小于等于hash1[s[right]]是就说明是一个有效字符 出窗口 if(right-left1nhash2[s[left]]–hash1[s[left]]) count–; 判断减掉的这个 hash2[s[left]]–,是不是小于等于hash1[s[right]]是就说明是一个有效字符 更新left if(countn) ret.push_back(left); class Solution { public:vectorint findAnagrams(string s, string p) {int ms.size(),np.size();unordered_mapchar,int hash1; for(auto e : p) hash1[e]; unordered_mapchar,int hash2;int count0;vectorint ret;for(int left0,right0;rightm;right){//进窗口if(hash2[s[right]]hash1[s[right]]) count;//出窗口if(right-left1nhash2[s[left]]–hash1[s[left]]) count–;//更新leftif(countn) ret.push_back(left);}return ret;} }; 总结 1.这题很难首先就是考虑暴力求解问题对于字符串s里面找p的异位词就是分别设置两个指针left和right从最左边开始找每次right-left1p.size()的时候就判断这个字串是不是跟p的异位词相同可以考虑把他门都存在两个hash数组中进行判断字符出现的次数是不是完全相同这是暴力每次当righe-left1p.size() 的时候那么当right这个时候left就也要每次就重新判断right从left位置开始重新把数组清空在重复上面步骤进行比较。 2.就是对于right-left1p.size()的时候进行比较这个时候不用right回退只需要leftright也不用清空hash2表只需要删除hash2[s[left]]–,并且hash2[[right]],让left指针前进就行相当于增加一个删除一个字符这就是典型的滑动窗口left和right都不会回退一直向前 ,并且满足进窗口当right-left1m 的时候让left在出窗口即可。可是这样时间复杂度还是很高 3.那么就考虑用count计数器来记录有效字符的个数每次只记录有效字符的个数当 if(hash2[s[right]]hash1[s[right]]) count; 减也是只有减去的是有效字符count才–  if(right-left1m) if(hash2[s[left]]–hash1[s[left]]) count–; 并且只在right-left1m 超过这个范围的时候才发生那么每次只需要判断有效字符个数达到p.size()的时候才就可以增加数据 7.串联所有单词的⼦串hard 这一题简直就是跟上一题找异位词百分之99都一样所以一定要弄懂上一题。 题目意思任然是要在words中的每个单词都以任意顺序组合然后再s里面找到这种组合的字串返回所有满足条件的下标。 解析 1.暴力 就是设置两个指针left 和 right 然后往后判断left 到 right 这个区间的字符串是不是能够等于words组合成的顺序显然这是绝对不可取的要进行优化。 2.优化 小demo看到这种任意组合的字符串我们不可能无序的组合然后在s里面找字串去进行对比这肯定不可取那么我们就要跟上题大优化一样设置计数器count 来记录有效字符串的个数这样就可以很方便的进行记录。 可以看出我们只需要讲words里面的字符串设置成a,b这种字符因为words里面单词的长度都是相等的那么设置int mwords[0].size() 来表示s里面假设的一个字符的长度就比如string strs.substr(left,m);就将str比作是一个字符。那么每次rightm.leftm 实际上每次都是跳过m个字符然后也是设计一个count来计数当这个str是有效字符的时候count设置_str满足有效字符的时候就leftm,出窗口。具体更上一题一模一样。 进窗口string str s.substr(right, len);                 //进窗口                 hash2[str];                 if(hash1.count(str) hash2[str] hash1[str]) count; //记录有效字符串的个数 出窗口if(right - left len m * len)                  {                     string _str s.substr(left, len);                     if(hash1.count(_str) hash2[_str] hash1[_str]) count–;                     hash2[_str]–;                     left len;                 } 更新leftif(count m) ret.push_back(left); class Solution { public:vectorint findSubstring(string s, vectorstring words) {int n s.size(), m words.size(), len words[0].size();unordered_mapstring, int hash1; for(auto e : words) hash1[e];vectorint ret;for(int i 0; i len; i){unordered_mapstring, int hash2;for(int left i, right i, count 0; right len n; right len){string str s.substr(right, len);//进窗口hash2[str];if(hash1.count(str) hash2[str] hash1[str]) count;//出窗口 固定的滑动窗口if(right - left len m * len) {string _str s.substr(left, len);if(hash1.count(_str) hash2[_str] hash1[_str]) count–;hash2[_str]–;left len;}if(count m) ret.push_back(left);}}return ret;} }; 总结 跟上一题固定滑动窗口大小简直一模一样不一样的就是上一题是滑动字符大小这次是滑动字符串大小 1.任然是设置两个hash表进行存入字符串用count来记录有效字符串的个数 2.区别就是在进窗口的时候要设置strs.substr(right,m); 在出窗口的时候设置_strs.substr(left,m); 3.优化就是要对hash1里面是否存在str 和 _str 进行判断这样可以减少查询时间 8.最⼩覆盖⼦串hard 经过上面那么多题的磨练这题是我为数不多的自信题调试了两个小时第一次自己解决一道困难题其实相对来说还是比较简单的。 题目意思就是找到最小字串要涵盖t中的全部字符可以重复包含。 解析 1.暴力 任何优化都是通过暴力推导的所以暴力真的很重要。 暴力就是无脑遍历s找到字符串长度要大于等于t.size() 然后进行比较如果包含全部t的字符就记录长度len直到求出最短长度。肯定会超时而且暴力不好实现所以还是要优化。 2.优化 那么还是双指针问题只要right判断有一个有效字符那么count直到包含所有的字符就开始更新len但是有很多细节问题比如 1).在len 比 s.size() 还要长明显就是没有进入该条件判断只能返回空串 2).在执行一次后 可能存在 sbba tab 这种情况那么必须要保证 left继续所以这个判断应该在while里面判断才行这样count 的种类数没有减少说明字串任然可以减少 3.存在saa taa 说明 可能会加入一个a count就满足种类达标了那么并不能就这样返回值所以还要判断只有在lent.size()的时候才可以采取否则就未达标。 进窗口       if (hash1.count(s[right]) hash2[s[right]] hash1[s[right]]) count; 出窗口 while (lenmcount hash1.size())         {             if (lenmlen right - left 1)             {                 len right - left 1;                 _left left;             }             if (hash1.count(s[left]) –hash2[s[left]] hash1[s[left]]) count–;             while (left n hash2[s[left]] 0) left;//跳过非种类字符         } 更新lenif(lenn) return ;     return s.substr(_left, len); class Solution { public:string minWindow(string s, string t) {int n s.size(), m t.size();if (n m) return ;unordered_mapchar, int hash1; for (auto e : t) hash1[e];unordered_mapchar, int hash2;int _left 0, len INT_MAX;int left 0, right 0;while (right n hash1.count(s[right]) 0) right, left;if (left n || right n) return ;int count 0;//记录种类for (right; right n; right){//进窗口if (hash1.count(s[right]) hash2[s[right]] hash1[s[right]]) count;//出窗口while (lenmcount hash1.size()){if (lenmlen right - left 1){len right - left 1;_left left;}if (hash1.count(s[left]) –hash2[s[left]] hash1[s[left]]) count–;while (left n hash2[s[left]] 0) left;//跳过非种类字符}}if(lenn) return ;return s.substr(_left, len); } }; 因子都是成对出现的那么我们就只需要在for里面判断 x*x n  那么就判断是否有一个m%x0 那么当xk 就满足另一个因子就是 m / x k 就也会满足。 总结一下“滑动窗口”问题其实也就是模板问题只要能明白“该问题是同向的双指针问题”那么就可以往滑动窗口靠就是“查找子数组”就分三大点进窗口_出窗口_更新len 我觉得我自己的进步挺大的希望对你也有帮助哦~