wordpress去掉搜索框,做seo前景怎么样,笔记模板wordpress,wordpress版权信息上方图片个人主页#xff1a;C忠实粉丝 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 C忠实粉丝 原创 滑动窗口(2)_无重复字符的最长字串 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记#xff0c;欢迎大家在评论区交流讨论#x1f48c; 目… 个人主页C忠实粉丝 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 C忠实粉丝 原创 滑动窗口(2)_无重复字符的最长字串 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记欢迎大家在评论区交流讨论 目录 1. 题目链接:
2. 题目描述 :
3. 解法 : 解法一(暴力枚举) : 算法思路 : 具体步骤 : 代码展示 : 结果分析 : 解法二(滑动窗口) : 算法思路 : 图解流程: 代码展示: 结果分析: 滑动窗口的正确性: 时间复杂度分析: 1. 题目链接:
OJ链接:无重复字符的最长字串
2. 题目描述 :
给定一个字符串 s 请你找出其中不含有重复字符的 最长 子串的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。提示
0 s.length 5 * 104s 由英文字母、数字、符号和空格组成
3. 解法 : 解法一(暴力枚举) : 算法思路 : 枚举[从每一个位置]开始往后,无重复字符的字串可以到达什么位置.找出其中长度最大的即可. 在往后寻找无重复字串能到达的位置时,可以利用[哈希标]统计出字符出现的频次,来判断什么时候字串出现了重复元素. 具体步骤 : 定义两个指针i,j遍历数组j,向后移动寻找与i重复的数j找到与i相同的数,更新字串长度.然后i,j i,重新重新寻找下一个数的最长无重复字串 代码展示 :
class Solution {
public:int lengthOfLongestSubstring(string s) {int len 0, n s.size();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;len max(len, j - i 1); }}return len;}
}; 结果分析 : !!!!!!!!!!!!!!!!!!!!!! 居然过了?这已经是第二个算法题能直接用暴力通过了 还是老样子,分析一下题目的数据范围: 0 s.length 5 * 104 字符串的长度区间范围:[0, 5*10^4],没超过10^5就给了暴力枚举的机会 我们暴力枚举的时间复杂度为O(N^2),这样数据级别大于10^9小于10^10是有机会通过的. 如果这道题更狠的话,直接把数据修改为10^5之内的字符,那我们的暴力枚举直接退役了 解法二(滑动窗口) : 算法思路 :
我们发现暴力算法真的很无脑,比如: 研究的对象依旧是一段连续的区间,因此继续使用[滑动窗口]思想来优化. 让滑动窗口满足: 窗口内所有元素都是不重复的. 做法: 右端元素right进入窗口的时候,哈希表统计这个字符的频次: 如果这个字符出现的频次超过1,说明窗口内有重复元素,那么就从左侧开始划出窗口.直到right这个元素的频次变为1,然后更新结果. 如果没有超过1,说明当前窗口没有重复元素,可以直接更新结果 基本思路: left 0, right 0;进窗口 ------ 让字符进入哈希表循环判断 窗口内出现重复字符(提前结束循环)出窗口 ------- 从哈希表中删除该字符更新结果 图解流程: 代码展示:
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;}
}; 结果分析: 滑动窗口的正确性:
我们这里使用滑动窗口解决了暴力枚举的重复遍历 时间复杂度分析: 时间复杂度: O(N) 空间复杂度: 我们开了一个hash数组,但只有128个空间,也就是常数级别,可以忽略不记,所以时间复杂度为O(1)
