159. Longest Substring With At Most Two Distinct C

spacewander 發布于2019-08-14 14:12 / 3020人閱讀

摘要：題目解法最重要的是把最后一次出現的這個的記在的里面。所以當出現不止兩個的數的時候，把這個最低的刪掉，把最的加就可以啦

題目：
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

解法：

//最重要的是把最后一次出現的這個char的index記在hashmap的value里面。所以當出現不止兩個distinc的數的時候，把這個value最低的char刪掉，把最lo的index加1就可以啦
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s.length() < 1) return 0;
        Map map = new HashMap();
        int lo = 0;
        int hi = 0;
        int maxLength = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (map.size() <= 2) {
                char c = s.charAt(i);
                map.put(c, i);
                hi++;
            }
            if (map.size() > 2) {
                int leftMost = s.length();
                for (int value : map.values()) {
                    leftMost = Math.min(leftMost, value);
                }
                lo = leftMost + 1;
                char c = s.charAt(leftMost);
                map.remove(c);
            }
            maxLength = Math.max(maxLength, hi - lo);
        }
        
        return maxLength;
    }

GPU云服務器云服務器 cdn159 Most Longest Substring

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

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

159. Longest Substring with At Most Two Distinct C

摘要：表示某個最后一次出現的地方可能只包含一種或者兩種只包含一種強制保持出現兩種保證，為了計算方便出現第三種的時候，直接計算出當前長度。 Given a string, find the length of the longest substring T that contains at most 2 distinct characters. For example, Given s = e...

liujs 2019-08-16 10:35 評論0 收藏0
[LeetCode] 159. Longest Substring with At Most Two

Problem Given a string s , find the length of the longest substring t that contains at most 2 distinct characters. Example 1: Input: ecebaOutput: 3Explanation: t is ece which its length is 3.Example ...

geekidentity 2019-08-16 13:56 評論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] Minimum Window Substring

摘要：使用而不是因為我們需要的是最值，中間值我們不在乎，所以一次收斂到最小。下面來三個需要查重并且記錄上次出現的位置，選擇以為例，走到用做檢查，發現出現過，把移到的下一個。是上個題目的簡易版，或者特殊版。這里聊一聊解一類問題，就是滿足某一條件的substring最值問題。最開始我們以Minimum Window Substring為例，并整理總結leetcode里所有類似題目的通解。 Gi...

Pines_Cheng 2019-08-14 17:17 評論0 收藏0
[Leetcode] Substring with Concatenation of All Wor

摘要：每次搜索中，我們通過哈希表維護一個窗口，比如中，我們先拿出。如果都不在數組中，那說明根本不能拼進去，則哈希表全部清零，從下一個詞開始重新匹配。 Substring with Concatenation of All Words You are given a string, s, and a list of words, words, that are all of the same...

adie 2019-08-14 12:46 評論0 收藏0