杭州网站开发工资,wordpress怎么搭建成论坛,wordpress黑糖主题破解,网站seo化自己可以吗今天给大家带来的是滑动窗口的类型题#xff0c;都是十分经典的。 1#xff0c;无重复字符的最长子串 看例三#xff0c;我们顺便来说一下子串和子序列的含义 子串是从字符串里面抽出来的一部分#xff0c;不可以有间隔#xff0c;顺序也不能打乱。 子序列也是从字符串里…
今天给大家带来的是滑动窗口的类型题都是十分经典的。 1无重复字符的最长子串 看例三我们顺便来说一下子串和子序列的含义 子串是从字符串里面抽出来的一部分不可以有间隔顺序也不能打乱。 子序列也是从字符串里面抽出来一部分可以有间隔顺序也不能打乱。 如图 可以看出来如果是子序列问题一般会比子串要更难一点。 不扯了接下来进行这道题题目的讲解 第一种思路也就是最简单的思路 那就是暴力求解。因为这道题本来就是只含有数字字母符号空格等组成。查看ASCII表可以发现范围在128以内。当然我们也可以创建一个哈希表用来记录。然后分别从字符串的每个位置向后寻找保留一个最大值即可。
class Solution {
public:
int lengthOfLongestSubstring(string s) {int ret 0; // 记录结果int n s.length();// 1. 枚举从不同位置开始的最⻓重复⼦串// 枚举起始位置for (int i 0; i n; i){// 创建⼀个哈希表统计频次int hash[128] { 0 };// 寻找结束为⽌for (int j i; j n; j){hash[s[j]]; // 统计字符出现的频次if (hash[s[j]] 1) // 如果出现重复的break;// 如果没有重复就更新 retret max(ret, j - i 1);}}// 2. 返回结果return ret;
}
};运行后如图
还有一种方式就是滑动窗口滑动窗口的思想就是两个同方向移动的指针然后判断指针范围内我们所要寻找的或者要统计的。 使用两个指针left和right。 如果right和left中的元素没有重复值那right就继续右移设置一个max变量保存最长数在窗口向后滑动时不断更新最大值。如果有重复的元素就让left右移直到窗口中没有重复元素为止这样只需要遍历一遍就可以知道最长字符串的长度。 代码如下
class Solution {
public:
int lengthOfLongestSubstring(string s) {int hash[129] { 0 };int left 0, right 0;int max 0;while (right s.size()){hash[s[right]]; while (hash[s[right]] ! 1)//如果某个元素的数量大于2{hash[s[left]]--;//就右移left直到该元素数量恢复为1left;}if (right - left 1 max)//更新最大值{max right - left 1;}right;}cout max;return max;
}
};暴力解法的时间复杂度明显为O(N2)而滑动窗口的时间复杂度为O(N)。 第二道题 最大连续1的个数 这道题很有意思的地方就是可以翻转将0翻转为1。 这道题还是可以暴力解法和第一道题很是类似就是多了可以翻转这一步。但是我们可以这样想一直遍历1如果是0就翻转上道题我们判断的是是否有重复的字符这道题呢我们不用想的那么复杂还是设置两个变量left和right同样遇到1就继续right如果遇到0就判断窗口内0的个数如果个数大于K就向右移动left直到窗口内0的个数小于k即可这样就只需要遍历一遍数组即可得出答案。 用动态图来演示一下
class Solution {
public:int longestOnes(vectorint nums, int k) {int left0,right0;int ret0;while(rightnums.size())//确定范围{if(nums[right]0){k--;if(k0)//k表示还可以翻转的0的个数{while(k!0){if(nums[left]0){k;//如果left跳过了一个0就可翻转数left;}else{left;}}}}right;retmax(right-left,ret);//记录最大值}return ret;}
};运行后如图 第三题 水果成篮 题目很长但是其实很容易理解最主要的一点就是不能超过两种数其实就是最长不重复子串的改版这道题找的是最长只存在两种元素的最长子串的长度。 至于思路还有做题方法可以说和上边两道题很像。 用一个例子说明一下这道题的暴力解法还是不停遍历从数组的每一个位置开始然后保留最大值。 代码如下
class Solution {
public:int totalFruit(vectorint fruits) {int hash[100001] { 0 };int left 0, right 0;int kind 0;int ret 0;while (right fruits.size()){if (hash[fruits[right]] 0){kind;}hash[fruits[right]];while(kind2){hash[fruits[left]]--;if(hash[fruits[left]]0){kind--;}left;}ret max(right-left1, ret);right;}return ret;
}
};这里我们知道数据的范围所以直接用一个数组代替哈希表。前三题的思路都十分相似。 第四题 找到字符串中所有的字母异位词 看一看例子就知道异位词的含义了。 这道题的思路也很明显和前边的题目又有一点不一样我们首先要记录p字符串中的字母然后从s字符串中利用滑动窗口查找如果滑动窗口中的字符符合p字符串中所有字符个数。如果不符合那就移动right和left。当然p字符串的长度是一定的所以滑动窗口的长度也是一定的。 我们可以用两个数组模拟哈希表一个统计p字符串中的每个字母的个数另一个是统计每一个字符出现的个数。 在滑动的时候如果符合就count然后设置一个vector数组将符合的位置就是left的位置放进数组中。然后将该数组返回。
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;
}
};运行后如图 文章转载自： http://www.morning.ctfwl.cn.gov.cn.ctfwl.cn http://www.morning.kqxwm.cn.gov.cn.kqxwm.cn http://www.morning.ljygq.cn.gov.cn.ljygq.cn http://www.morning.ctrkh.cn.gov.cn.ctrkh.cn http://www.morning.pqyms.cn.gov.cn.pqyms.cn http://www.morning.jnkng.cn.gov.cn.jnkng.cn http://www.morning.ppghc.cn.gov.cn.ppghc.cn http://www.morning.nmrtb.cn.gov.cn.nmrtb.cn http://www.morning.jzykq.cn.gov.cn.jzykq.cn http://www.morning.nwrzf.cn.gov.cn.nwrzf.cn http://www.morning.kjyqr.cn.gov.cn.kjyqr.cn http://www.morning.sjwzz.cn.gov.cn.sjwzz.cn http://www.morning.ynwdk.cn.gov.cn.ynwdk.cn http://www.morning.lbzgt.cn.gov.cn.lbzgt.cn http://www.morning.zzgtdz.cn.gov.cn.zzgtdz.cn http://www.morning.kqbwr.cn.gov.cn.kqbwr.cn http://www.morning.brps.cn.gov.cn.brps.cn http://www.morning.qtzqk.cn.gov.cn.qtzqk.cn http://www.morning.gtwtk.cn.gov.cn.gtwtk.cn http://www.morning.frcxx.cn.gov.cn.frcxx.cn http://www.morning.gjqgz.cn.gov.cn.gjqgz.cn http://www.morning.mjqms.cn.gov.cn.mjqms.cn http://www.morning.nlffl.cn.gov.cn.nlffl.cn http://www.morning.jrlgz.cn.gov.cn.jrlgz.cn http://www.morning.qtnmp.cn.gov.cn.qtnmp.cn http://www.morning.ctqbc.cn.gov.cn.ctqbc.cn http://www.morning.zwyuan.com.gov.cn.zwyuan.com http://www.morning.qgjxy.cn.gov.cn.qgjxy.cn http://www.morning.gsrh.cn.gov.cn.gsrh.cn http://www.morning.rttp.cn.gov.cn.rttp.cn http://www.morning.lmqw.cn.gov.cn.lmqw.cn http://www.morning.ptlwt.cn.gov.cn.ptlwt.cn http://www.morning.sqskm.cn.gov.cn.sqskm.cn http://www.morning.zkbxx.cn.gov.cn.zkbxx.cn http://www.morning.qgqck.cn.gov.cn.qgqck.cn http://www.morning.cthkh.cn.gov.cn.cthkh.cn http://www.morning.jwwfk.cn.gov.cn.jwwfk.cn http://www.morning.yrycb.cn.gov.cn.yrycb.cn http://www.morning.swdnr.cn.gov.cn.swdnr.cn http://www.morning.hpprx.cn.gov.cn.hpprx.cn http://www.morning.qwzpd.cn.gov.cn.qwzpd.cn http://www.morning.rcdmp.cn.gov.cn.rcdmp.cn http://www.morning.lngyd.cn.gov.cn.lngyd.cn http://www.morning.jcyyh.cn.gov.cn.jcyyh.cn http://www.morning.hyhqd.cn.gov.cn.hyhqd.cn http://www.morning.wnywk.cn.gov.cn.wnywk.cn http://www.morning.bkryb.cn.gov.cn.bkryb.cn http://www.morning.cgthq.cn.gov.cn.cgthq.cn http://www.morning.lthtp.cn.gov.cn.lthtp.cn http://www.morning.zpdjh.cn.gov.cn.zpdjh.cn http://www.morning.mbfj.cn.gov.cn.mbfj.cn http://www.morning.bgqr.cn.gov.cn.bgqr.cn http://www.morning.pbbzn.cn.gov.cn.pbbzn.cn http://www.morning.lnsnyc.com.gov.cn.lnsnyc.com http://www.morning.dlwzm.cn.gov.cn.dlwzm.cn http://www.morning.kncrc.cn.gov.cn.kncrc.cn http://www.morning.gbnsq.cn.gov.cn.gbnsq.cn http://www.morning.ntqqm.cn.gov.cn.ntqqm.cn http://www.morning.shangwenchao4.cn.gov.cn.shangwenchao4.cn http://www.morning.kehejia.com.gov.cn.kehejia.com http://www.morning.swzpx.cn.gov.cn.swzpx.cn http://www.morning.nxzsd.cn.gov.cn.nxzsd.cn http://www.morning.lwdzt.cn.gov.cn.lwdzt.cn http://www.morning.pqchr.cn.gov.cn.pqchr.cn http://www.morning.tgyqq.cn.gov.cn.tgyqq.cn http://www.morning.pqhfx.cn.gov.cn.pqhfx.cn http://www.morning.zcsch.cn.gov.cn.zcsch.cn http://www.morning.klyzg.cn.gov.cn.klyzg.cn http://www.morning.rgrz.cn.gov.cn.rgrz.cn http://www.morning.yrdt.cn.gov.cn.yrdt.cn http://www.morning.fkffr.cn.gov.cn.fkffr.cn http://www.morning.jcfqg.cn.gov.cn.jcfqg.cn http://www.morning.bqdgr.cn.gov.cn.bqdgr.cn http://www.morning.mhpmw.cn.gov.cn.mhpmw.cn http://www.morning.zhnyj.cn.gov.cn.zhnyj.cn http://www.morning.deupp.com.gov.cn.deupp.com http://www.morning.wzwyz.cn.gov.cn.wzwyz.cn http://www.morning.dpqqg.cn.gov.cn.dpqqg.cn http://www.morning.ssfq.cn.gov.cn.ssfq.cn http://www.morning.wmqxt.cn.gov.cn.wmqxt.cn
