LeetCode——Longest Substring Without Repeating Char

forsigner 發布于2019-08-26 13:31 / 3217人閱讀

摘要：原問題我的沙雕解法無重復字母存在重復字母挨打最暴力的無腦解法，耗時。。。

原問題

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

圖片來源：https://www.cnblogs.com/wangk...

GPU云服務器云服務器 Repeating Without Longest LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/108979.html

[Leetcode]Longest Substring Without Repeating Char

摘要：解題思路本題借助實現。如果字符未出現過，則字符，如果字符出現過，則維護上次出現的遍歷的起始點。注意點每次都要更新字符的位置最后返回時，一定要考慮到從到字符串末尾都沒有遇到重復字符的情況，所欲需要比較下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...

awesome23 2019-08-16 10:26 評論0 收藏0
[LeetCode] Longest Substring Without Repeating Cha

摘要：建立數組，存儲個字符最近一次出現的位置。首次出現某字符時，其位置標記為，并用無重復字符計數器記錄無重復字符的長度，再在更新其最大值。循環完整個字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...

CoderStudy 2019-08-14 15:48 評論0 收藏0
leetcode 3 Longest Substring Without Repeating Cha

摘要：題目詳情題目要求輸入一個字符串，我們要找出其中不含重復字符的最長子字符串，返回這個最長子字符串的長度。對于字符串中的每一個字符，先判斷中是否已經存在這個字符，如果不存在，直接將添加到，如果已存在，則新的字符串就從不含前一個字符的地方開始。題目詳情 Given a string, find the length of the longest substring without repe...

xcold 2019-08-15 14:21 評論0 收藏0
[Leetcode] Longest Substring Without Repeating Cha

摘要：哈希表是最自然的想法。在遍歷字符串時，我們先根據哈希表找出該字符上次出現的位置，如果大于等于子字符串首，便更新子字符串首。結束后，將該字符新的位置放入哈希表中。 Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/... Given a string, find the ...

FleyX 2019-08-14 12:18 評論0 收藏0
[LeetCode] Longest Substring Without Repeating Cha

Problem Given a string, find the length of the longest substring without repeating characters. Examples Given abcabcbb, the answer is abc, which the length is 3. Given bbbbb, the answer is b, with the...

graf 2019-08-19 10:52 評論0 收藏0