<fieldset id="io0wy"></fieldset>

<del id="io0wy"></del>

[Leetcode]Longest Substring Without Repeating Char

awesome23 發布于2019-08-16 10:26 / 3451人閱讀

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

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.

1.解題思路

本題借助HashMap實現。
1）如果字符未出現過，則put(字符，index);
2) 如果字符出現過，則維護len=上次出現的index-遍歷的起始點。
那問題就到了如何去定義遍歷的起始點呢，我們當然可以從0開始，然后每次加1，但是通過下面的例子，我們很容易就發現這樣會有很多情況冗余：
“abcdecf”
我們從index 0開始，到第二個字符c-index5，我們會發現已經存在，所以len,5-0=5；但如果我們之后index從1開始，我們會發現必然還會在index5這邊停止，為了減少這種冗余，我們想到可以在一次重復后，將start置為重復元素Index+1，這里就是index3-d, 這樣我們在碰到已經存在的字符時，就要再加上一個判斷，看其上一次出現是否在start之前，如果在start之前，則不作考慮，直接Put進新的位置；如果是在start之后，則就表明確實遇到了重復點。
注意點：
1）每次都要更新字符的位置；
2）最后返回時，一定要考慮到從start到s.length(字符串末尾)都沒有遇到重復字符的情況，所欲需要比較下maxLen和s.length()-start的大小。

2.代碼

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0) return 0;
        HashMap hm=new HashMap();
        int start=0;
        int maxLen=1;
        for(int i=0;i=start){
                int len=i-start;
                maxLen=Math.max(maxLen,len);
                start=hm.get(s.charAt(i))+1;
            }
            hm.put(s.charAt(i),i);
        }
        return Math.max(maxLen,s.length()-start);
    }
}

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

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

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

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

摘要：建立數組，存儲個字符最近一次出現的位置。首次出現某字符時，其位置標記為，并用無重復字符計數器記錄無重復字符的長度，再在更新其最大值。循環完整個字符串后，返回最大值。 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