网站搭建联系方式,西安seo培训学校,兰州网站建设最新招聘信息,incapsula wordpress3.给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”#xff0c;所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3: 输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。 我的思路遍历字符串用 hashMap 记录每个字符出现的索引当出现重复字符时结算一次长度然后将遍历索引更新到重复字符出现处以它的后一位为新起点重新计算无重复子串长度。比如 “abcab”当遍历到 i 为 3 时发现 a 之前有重复过所以先结算当前长度 3下一轮重新计算子串长度并且从 a 后一位即 b 开始重新计算。 public int lengthOfLongestSubstring(String s) {MapCharacter,Integer map new HashMap();int ans 0;// 计算每一轮子串长度int temp 0;for(int i0;is.length();i){char c s.charAt(i);// 找到重复字符if(map.containsKey(c)){// 让下一轮遍历从最近重复字符下一位开始i map.get(c);// 记得清空 map不然直接就又重复了map.clear();// 结算长度ans Math.max(ans,temp);// 长度归零temp0;continue;}map.put(c,i);temp;}ans Math.max(ans,temp);return ans;}他人解法1实际上如果以动态规划的角度来看更加清晰明了设 f(x) 为以字符串第 x 位结尾的最长无重复子串长度(以下简称答案好了)。当计算 f(j) 时根据本题关键是否有重复字符就划分成了两种情况首先假设我当前正在计算长度的子串区间为 i~j或者形象点 2~5字符串为 ababcbcd此时如果在我的区间即 abcb 内有和 x 处即位置 5 处的 b 重复的字符比如位置 3 处的 b 那么我这一轮的子串长度就为 5-3 也就是 cb 这一段的长度否则就说明起码我这段区间没有重复字符那我就可以在之前的基础上 1 了即 dp[j-1]1。比如 abcd我从 a 开始往后找一直没有重复的字符答案长度就一直累加。总结一下就是对于 dp[j]设有 s[j] 的最近重复字符 s[i]如果 i 在 dp[j-1] 的区间外没有重复字符也属于在区间外的情况即 dp[j-1]j-i画两个线段就知道关系了dp[j-1] 就是当前区间长度 xj-i 就是重复字符到当前区间尾端的长度 yy x 就说明重复字符 i 在当前区间起点左侧即不在当前区间那 dp[j] dp[j-1]1否则 dp[j] j-i i----------jx------j dp[j-1]public int lengthOfLongestSubstring(String s) {MapCharacter,Integer map new HashMap();int ans 0;// temp 其实就是 dp[j-1]不需要定义 dp 数组int temp 0;for(int j0;js.length();j){char c s.charAt(j);// 当前区间没有重复字符就返回 -1// 因为 dp[j-1] j 恒成立(因为你最长的情况下一直没有重复字符长度也才 j-1)// 那 i 取负数的话 dp[j-1] j-i 也是必定成立的int i map.getOrDefault(c,-1);map.put(c,j);temp temp j-i?temp1:j-i;ansMath.max(temp,ans);}return ans;}他人解法2而其实不用 map 也可以那就遍历寻找最近的重复字符从当前遍历到的 s[j] 的前一位即 j-1 开始往前找重复字符。 public int lengthOfLongestSubstring(String s) {int ans 0;// temp 其实就是 dp[j-1]不需要定义 dp 数组int temp 0;for(int j0;js.length();j){int ij-1;// 这里也能把 i0 优化成 i j-temp// 因为不需要每次都找到s[0]根据我们上面两条线段的分析// i 只要小于 x 了就说明当前区间不包含重复字符了while(i0 s.charAt(i) ! s.charAt(j))i--;temp temp j-i?temp1:j-i;ansMath.max(temp,ans);}return ans;}他人解法 3在解法 1 的基础上来看其实 temp 1 可以看成当没有重复字符时左端点 i 固定j 随着遍历不断 1 后j-i 也不断 1当发现重复字符时更新 i 即可然后答案依旧是取 j-i。 public int lengthOfLongestSubstring(String s) {MapCharacter, Integer map new HashMap();// i当前区间左端点int i -1, ans 0, len s.length();for(int j 0; j len; j) {// 为什么不是直接 map.get(s.charAt(j))// 因为比如 abba发现 b 重复时已经把 i 更新到 1// 然后再发现 a 时其实那个 a 已经不在当前区间了// 也就是我们已经抛弃了前面的 ab只计算 ba 的长度即可// 也就是只理会大于当前区间左端点的重复字符即可所以要 maxif(map.containsKey(s.charAt(j)))i Math.max(i, map.get(s.charAt(j)));map.put(s.charAt(j), j); ans Math.max(ans, j-i); }return ans;}
