亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

RyanHoo / 2079人閱讀

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

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

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

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

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

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

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

期間記錄不重復(fù)的最大長度.

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

由于使用了HashSet, 每個元素訪問不超過兩次(添加與移除), 所以算法時間復(fù)雜度為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方法執(zhí)行的測試結(jié)果為:

1
3
4
2
3
3

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/66376.html

相關(guān)文章

  • leetcode 3 Longest Substring Without Repeating Cha

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

    xcold 評論0 收藏0

  • LeetCode——Longest Substring Without Repeating Char

    摘要：原問題我的沙雕解法無重復(fù)字母存在重復(fù)字母挨打最暴力的無腦解法，耗時。。。 原問題 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 評論0 收藏0

  • [Leetcode] Longest Substring Without Repeating Cha

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

    FleyX 評論0 收藏0

  • [Leetcode] Longest Substring with At Most 2 Distin

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

    imccl 評論0 收藏0

  • [LeetCode] Longest Substring Without Repeating Cha

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

    CoderStudy 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<