[LintCode] Longest Substring Without Repeating Cha

Scliang 發布于2019-08-14 15:19 / 2643人閱讀

摘要：哈希表法雙指針法只有當也就是時上面的循環才會結束，，跳過這個之前的重復字符再將置為

Problem

Given a string, find the length of the longest substring without repeating characters.

Example

For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.

For "bbbbb" the longest substring is "b", with the length of 1.

Note Solution

1. 哈希表法

HashMap Method I

  public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap map = new HashMap();
        int count = 0, start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                int index = map.get(s.charAt(i));
                for (int j = start; j <= index; j++) {
                    map.remove(s.charAt(j));
                }
                start = index + 1;
            }
            map.put(s.charAt(i), i);
            count = Math.max(count, i - start + 1);
        }
        return count;
    }
}

HashMap Method II

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        HashMap map = new HashMap<>();
        int max = 1, start = 0;
        for (int i = 0; i < s.length(); i++) {
            Character cur = s.charAt(i);
            Integer rep = map.get(cur);
            if (rep != null && rep >= start) {
                max = Math.max(max, i-start);
                start = rep+1;
            }
            map.put(cur, i);
        }
        return Math.max(s.length()-start, max);
    }
}

2. 雙指針法

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start = 0, end = 0, count = 0;
        boolean[] mark = new boolean[256];
        while (end < s.length()) {
            if (!mark[s.charAt(end)]) {
                mark[s.charAt(end)] = true;
                count = Math.max(count, end-start+1);
                end++;
            }
            else {
                while (mark[s.charAt(end)]) {
                    mark[s.charAt(start)] = false;
                    start++;
                }
                
                //只有當s.charAt(start) == s.charAt(end)
                //也就是mark[s.charAt(end)] == false時
                //上面的循環才會結束，start++，跳過這個之前的重復字符
                //再將mark[s.charAt(end)]置為true
                
                mark[s.charAt(end)] = true;
                end++;
            }
        }
        return count;
    }
}

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

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

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

[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
[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 Char

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

awesome23 2019-08-16 10:26 評論0 收藏0