内容简介:Given a string, find the length of the longest substring without repeating characters.挨打:最暴力的无脑解法,耗时672ms。。。参考了排名较前的答案,多数是贪心思想,以下摘抄一位的代码并加上学习的注释
原问题
Given a string, find the length of the longest substring without repeating characters.
Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2: Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3: Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
我的沙雕解法
var lengthOfLongestSubstring = function(s) { let recordObj = {}; let length = s.length; let max = 0; for(let i = 0; i < length; i++){ let record = 0; for(let g = i; g < length; g++){ if(recordObj[s[g]] === undefined){//无重复字母 recordObj[s[g]] = true; record++; }else{//存在重复字母 recordObj = {}; break; } } max = record > max? record:max; if(max === length){break;} } return max; };
挨打:最暴力的无脑解法,耗时672ms。。。
贪心解法学习
参考了排名较前的答案,多数是贪心思想,以下摘抄一位的代码并加上学习的注释
/** * 通过i,j指针计算子序列长度 * j指针:表示当前循环的字母,i指针:表示起点 * map用于记录出现过的字母的相邻下标,给予i新的起点 * 重复字母出现时,比较当前起点与map的记录位置,取较大值,保证连续子序列,同时体现贪心:求 * 当前可求得的最长子序列 **/ var lengthOfLongestSubstring = function(s) { var n = s.length, ans = 0; var map = new Map(); // 记录出现过字母的相邻下标 // try to extend the range [i, j] for (var j = 0, i = 0; j < n; j++) { if (map.has(s.charAt(j))) { //若此字母在之前的循环中出现过 i = Math.max(map.get(s.charAt(j)), i); //保证连续子序列,同时体现贪心 } ans = Math.max(ans, j - i + 1); //比较 map.set(s.charAt(j), j + 1); //记录字母的相邻位置 } return ans; };
此算法耗时108ms
百度到一张图片很有利于理解
举例:qpxrjxkltzyx
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- LeetCode——Longest Substring Without Repeating Characters
- leetCode 3 Longest Substring Without Repeating Characters
- [LeetCode] 3. Longest Substring Without Repeating Characters 题解
- LeetCode 第3题 Longest Substring Without Repeating Characters【滑动窗口】(Java)
- Leetcode基础刷题之PHP解析(3. Longest Substring Without Repeating Characters )
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。