松江php网站开发培训,wordpress搬家后乱码,长沙设计网站建设,钢材网站建设给定一个字符串#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”#xff0c;所以其长度为 3。 示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”#x… 给定一个字符串请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3:
输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。
动态规划解
dp[i]到以第i个字符结尾的不包含重复字符的最大长度 对于第i个字符 1、第i个字符从未出现过dp[i]dp[i-1]1 2、第i个字符出现过找到第i个字符最近一次出现的位置index(从第i个往前找),记两个距离为di-index 【a】、d dp[i-1],即这个字符出现在以第i-1个字符结尾的不含重复字符的字符串中,则dp[i]d,表示从第最近一次出现后重新计算长度 例如 i: 0 1 2 3 4 5 s: 1 2 3 4 5 4 dp: 1 2 3 4 5 2 最后的这个2 5 - 3最近一次出现的i 【b】、ddp[i-1],即这个字符没有出现在以第i-1字符结尾的不含重复的最大长度字符串中。 dp[i] dp[i-1] 1; 例如 i: 0 1 2 3 4 5 6 s: 1 2 3 4 5 4 1 dp: 1 2 3 4 5 2 3 s最后的这个1虽然在i0的位置出现过但是由于d6-06dp[5],所以dp[6]dp[5]1,也就是说我们的子串已经重新更新了。
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_setchar myset;int sz s.size();int ans 1;if (sz 0) return 0;vectorint dp(sz, 0);dp[0] 1;for (int i 0;i sz;i) //起点{//如果第i个字符出现过if (myset.find(s[i]) ! myset.end()){if (i 1){int index get_index(s, s[i],i); if (index -1) index 0;int d i - index;if (d dp[i - 1]) dp[i] d;else dp[i] dp[i - 1] 1;}}//如果没有出现过记录下来else{myset.insert(s[i]);if (i 1){dp[i] dp[i - 1] 1;}}ans max(ans, dp[i]);}return ans;}int get_index(string s, char x,int start) {int sz s.size();if (sz 0) return -1;for (int i start-1;i 0 ;i--){if (s[i] x) return i;}return -1; //没有找到}
};参考https://zhuanlan.zhihu.com/p/112545613进行优化; f[i]以原字符串s中以位置i的字符s[i]为右边界时的最优左边界 例如样例 a b c a b c b b 对应的f数组为 f[0] 0左边界为第一个a对应子串为a f[1] 0左边界为第一个a对应子串为ab f[2] 0左边界为第一个a对应子串为abc f[3] 1左边界为第一个b对应子串为bca f[4] 2左边界为第一个c对应子串为cab f[5] 3左边界为第二个a对应子串为abc f[6] 5左边界为第二个c对应子串为cb f[7] 7左边界为最后一个b对应子串为b f[0] 0; 对于f[i],只需要考察f[i-1]到i-1这个区间中是否出现过s[i] 如果没有出现过则f[i]f[i-1] 如果出现过那么必然只出现了一次因为f[i-1]到i-1这个区间中必然不存在重复字符于是设s[i]出现的位置为pos则f[i]pos1;在重复的字符后面的一个字符作为新的起始点。 可以发现左边界的更新是单调递增的因此s中每个字符最多也只会遍历一遍时间复杂度为O(n)。 由于f[i]的更新只与f[i-1]有关因此不需要维护整个数组。 class Solution(object):def lengthOfLongestSubstring(self, s)::type s: str:rtype: intleft 0res 0for right,char in enumerate(s):pos s.find(char,left,right)if pos 0:left pos1else: left leftres max(res,right-left1) return res滑动窗口解
其实和dp第一种方法类似 滑动窗口的核心思路如下 比如输入字符串为abcdecfg字串 abcde 满足题目要求当新加入 c 时字串变成了 abcde c字符 c 重复了不满足要求。这时候只需要将第一个重复的字符 c 连同之前的字符丢掉变成 de c就又能满足要求了。每新加一个字符都更新最长字串的长度遍历完一遍之后即可得到答案。 问题在于如何丢掉第一个重复字符连同之前的字符其实我们不用真的丢掉而是可以维护一个左边界值 left 有重复字符的话就把 left 更新为重复字符的下一个位置假装丢掉了它和之前的字符。 参考链接:https://blog.csdn.net/m0_37433111/article/details/108743399
class Solution {
public:int lengthOfLongestSubstring(string s) {int sz s.size();if (sz 0) return 0;int left0;int maxlen1;// val存放字符在原字符串的索引unordered_mapchar,int u_map;for (int i 0;i sz;i) //起点{//如果有重复的字符左边界更新到重复的字符后面一个if(u_map.find(s[i])!u_map.end()) left max(left,u_map[s[i]]1);//如果没有重复的字符左边界保持不变也就是leftleft,可以省略不写//将s[i]插入、u_map[s[i]] i; //如果有重复的则将坐标更新为靠后的坐标// 更新最长子串的长度maxlen max(maxlen,i-left1);}return maxlen;}
};
