Leetcode 3 Longest Substring Without Repeat... 最長無

RyanHoo 發布于2019-08-14 17:01 / 2026人閱讀

摘要：難度題意是求最長無重復子串給出一個字符串從所有子串中找出最長且沒有重復字母的子串的長度我的解法是以為例使用一個記錄當前子串遇到的所有字符用一個游標從頭開始讀取字符加入到中如果碰到了重復字符遇到了重復則從當前子串的頭部的字符開始將該字符從中移

Longest Substring Without Repeating Characters
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 length of 1.
Given "pwwkew", 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.

難度: Medium

題意是求最長無重復子串, 給出一個字符串, 從所有子串中, 找出最長, 且沒有重復字母的子串的長度.

我的解法是: (以abcbcdabb為例)

使用一個set, 記錄當前子串遇到的所有字符.

用一個游標, 從頭開始讀取字符, 加入到set中.(a, ab, abc)

如果碰到了重復字符(i=3, 遇到了b, 重復), 則從當前子串的頭部的字符開始, 將該字符從set中移除, 直到移除了當前這個重復字符為止. (abc, bc, c, cb)

期間記錄不重復的最大長度.

遍歷完整個字符串后, 輸出最大長度.

由于使用了HashSet, 每個元素訪問不超過兩次(添加與移除), 所以算法時間復雜度為O(n).

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // a set to record chars for current substring
        Set cset = new HashSet();
        // length of longest non-repeat substring
        int lgst = 0;
        // length of current substring
        int curLen = 0;
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            curLen++;
            // if encounters a duplicate character
            if (cset.contains(c)) {
                // record non-repeat length
                lgst = (curLen - 1) > lgst ? (curLen - 1) : lgst;
                // reduce character from the head of current substring,
                // until current repeat letter is removed
                for (int j = i - cset.size(); j < i; j++) {
                    curLen--;
                    cset.remove(s.charAt(j));
                    if (s.charAt(j) == c) {
                        break;
                    }
                }
            }
            cset.add(c);
        }
        lgst = curLen > lgst ? curLen : lgst;
        return lgst;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.lengthOfLongestSubstring("bbbbbb"));
        System.out.println(s.lengthOfLongestSubstring("abcabcbb"));
        System.out.println(s.lengthOfLongestSubstring("abcbcdabb"));
        System.out.println(s.lengthOfLongestSubstring("aab"));
        System.out.println(s.lengthOfLongestSubstring("dvdf"));
        System.out.println(s.lengthOfLongestSubstring("advdf"));
    }
}

main方法執行的測試結果為:

1
3
4
2
3
3

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

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

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

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 Char

摘要：原問題我的沙雕解法無重復字母存在重復字母挨打最暴力的無腦解法，耗時。。。原問題 Given a string, find the length of the?longest substring?without repeating characters. Example 1: Input: abcabcbb Output: 3 Explanation: The answer is a...

forsigner 2019-08-26 13:31 評論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 with At Most 2 Distin

摘要：最新思路解法哈希表法復雜度時間空間思路我們遍歷字符串時用一個哈希表，但這個哈希表只記錄兩個東西，一個字母和它上次出現的時的下標，另一個字母和它上次出現時候的下標。這個通過用哈希表記錄字母上次出現的下標，來維護一個窗口的方法也可以用于。 Longest Substring with At Most Two Distinct Characters 最新思路解法：https://yanjia...

imccl 2019-08-14 12:36 評論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