网站前置审批,大前端 wordpress,哈尔滨网页设计师招聘,做网站能用ai做吗目录
题目#xff1a; 无重复字符的最长子串
1. 题目解析
2. 算法原理
Ⅰ. 暴力枚举
Ⅱ. 滑动窗口#xff08;同向双指针#xff09;
3. 代码实现
Ⅰ. 暴力枚举
Ⅱ. 滑动窗口 题目#xff1a; 无重复字符的最长子串
1. 题目解析
题目截图#xff1a; 此题所说的…
目录
题目 无重复字符的最长子串
1. 题目解析
2. 算法原理
Ⅰ. 暴力枚举
Ⅱ. 滑动窗口同向双指针
3. 代码实现
Ⅰ. 暴力枚举
Ⅱ. 滑动窗口 题目 无重复字符的最长子串
1. 题目解析
题目截图 此题所说的子串与长度最小的子数组题目中所说的子数组相当于一个概念都是数组中连续的一段区别在于子串是在一个字符串中子数组是在一个整数数组中。 题目中要求找到一个没有重复字符的子串并返回它的长度。 所以看到这里有三个长度为3的子串且是最长的所以返回3。 这里可以看出全是b只能找到一个字符并返回长度1因为再往后扩展也是重复的了。 所以这道题的要求并要求返回什么如上面所示。 2. 算法原理
这道题也有两种解法的
暴力枚举滑动窗口
Ⅰ. 暴力枚举
暴力枚举也就是把所有子串都枚举出来枚举子串的时候以某一个位置为起点然后向后枚举再接着以另一个某一个位置为起点再向后枚举这里注意的是枚举并不是全部枚举而是当枚举一个位置时继续再向后枚举的时候如果发现有重复的字符出现那么就停止枚举也就是说以这个位置开头的只能枚举到这里了然后统计长度接下来才是枚举第二个开头的一直把所有情况枚举到最后找一个长度的最大值。 这里的长度为2。 这里长度为3通过上面题目解析中已经得知这里最长长度就是3. 固定每一个有可能的起始位置然后依次向后扩展直到扩展不能扩展为止然后统计一下长度把所有情况都枚举到再统计一下最大值。
不过这里我们都是通过肉眼观察它们是否有重复的但是程序中可不会直接就能观测到这里就需要处理是否重复的细节问题了可以借助开放定址法的hash表来解决重复问题只需要把对应的字母映射到表上遍历一个字符就让它映射到哈希表上然后表里字母对应位置的数据统计它出现的次数若是大于 1那么它就重复。
所以这里的解法暴力枚举哈希表表的数据存储的是字符出现的次数为了判断字符是否重复出现
这里时间复杂度ON²。
所以暴力枚举 先判断 right 指向的字符在不在 hash表 里也就是看表里对应的数据是不是大于 0不在就放进去然后 right 向后移动再接着判断 right 指向的元素在不在不在就放进去right 再向后移动重复上面的操作不在就在表里对应的位置 1然后 right 后移
再接着判断重复上面操作 判断不在重复上面操作 此时判断不在重复上面操作这时right指向了第二个字符a 当上面right 到 a 时字符先前已经存在于哈希表里了这时候就要停止枚举操作deabc的长度就是以d开头的能得到无重复字符串的子串的最长长度。
接下来让left换一个位置left后移动一位此时再让right回退至left的位置
接下来继续重复上面的操作直到把所有符合条件的情况枚举出来统计长度再获取最长的那个长度返回即可。 Ⅱ. 滑动窗口同向双指针
在上面暴力枚举种我们发现有些情况是可以优化的我们发现如下的情况 这时left再往下一个移动的时候这时到了字符a让right回退到left再继续枚举发现还是会到同一个a位置停止枚举当left跳过了第一个出现的字符a之后停止枚举的位置就发生变化了 也就是说
并且这里发现在这个区间内依次往后枚举起始位置的话因为终点是同样的这时子串的长度就会递减因此就可以让right不要拐回去了让right在该位置先不动先调整left让left跳过有重复的字符 暴力解法中left移动到新的位置的时候right就要回退至left的同位置但这里也可以有个优化也就是left跳过重复字符后right是没有必要回退至left的 因此我们发现这里left和right的移动方向是一致的也就是同向双指针 这里的窗口就是left和right区间内维护的无重复字符的子串让字符先进入窗口然后判断当有重复的字符的时候就让它出窗口 这里的解法就是利用规律使用滑动窗口来解决问题。
注意上面的情况每次都要更新结果结果就是字符串的子串的长度。
规律
当里面有重复的字符的时候让left先向右移动把出现的重复字符的位置之前的字符给跳过因为它们的最后终点都会为这个重复的字符的第二次出现的位置。当left到符合要求的位置时候right是不用回退的可以继续向后移动扩展该区间。
所以这里就可以同上一道题 长度最小的子数组 用滑动窗口的方法步骤解决
先定义 left 和 right 并都初始化为0充当窗口的左右端点。进窗口这里让字符串进入哈希表即可。判断当窗口里有重复的字符时候就要出窗口就是从哈希表中删除该字符注意在删除之后要再继续判断直到没有重复字符为止。进出窗口都需要更新结果符合要求的子串的长度取新旧结果中最大的那一个即可。直到right指向最右边为止就就结束了。 这里时间复杂度情况也同于 长度最小的子数组 的情况根据实际情况是每一步操作仅仅会让 right 向右移动 1 位或 left 向右移动 1 位直到 right 移动到最后的位置。最坏的情况就是两个指针都遍历了一遍该数组也就是2n次所以时间复杂度为:ON。
接下来实现两种方法的代码 3. 代码实现
题目链接无重复字符的最长子串 Ⅰ. 暴力枚举
时间复杂度ON²。
//暴力枚举
class Solution {
public:int lengthOfLongestSubstring(string s) {int n s.size();int len 0;for(int left 0; left n; left) //先固定起始位置{int hash[128] {0}; //将字符串中的字符出现次数映射到hash表for(int right left; right n; right)//依次从left位置向后枚举扩展区间{hash[s[right]];//让字符充当下标该位置字符出现就让它对应的hash值1if(hash[s[right]] 1) //大于1说明出现重复字符了{break; //直接退出循环}len max(len, right - left 1); //更新结果}}return len;}
};
提交记录 Ⅱ. 滑动窗口
时间复杂度ON。
//滑动窗口
class Solution {
public:int lengthOfLongestSubstring(string s) {int n s.size();int len 0;int hash[128] { 0 }; //使用数组模拟hash表//遇到重复的不需要让right回退了让left跳过重复的字符之后再处理right即可for(int left 0, right 0; right n; right) {hash[s[right]]; //进入窗口while(hash[s[right]]1) //判断{//大于1说明出现重复了hash[s[left]]--; //出窗口}len max(len,right-left1); //更新结果 }return len;}
};
提交记录 制作不易,若有不足之处或出问题的地方请各位大佬多多指教 感谢大家的阅读支持!
