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

資訊專欄INFORMATION COLUMN

Leetcode[76] Minimum Window Substring

suemi / 981人閱讀

LeetCode[76] Minimum Window Substring 
Given a string S and a string T, find the minimum window in S which
will contain all the characters in T in complexity O(n).


For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".
Hash Table + Two Pointer

復(fù)雜度
O(N),O(N)

思路
類似two pointer的想法。每次維護一個窗口。

代碼

public String minWindow(String s, String t) {
    int start = 0, len = Integer.MAX_VALUE;
    int[] times = new int[256];
    int[] stimes = new int[256];
    for(int i = 0; i < t.length(); i ++) {
        times[t.charAt(i)] ++;
    }
    int cnt = 0;
    int begin = -1, end = 0;
    for(int i = 0; i < s.length(); i ++) {
        char ch = s.charAt(i);
        stimes[ch] ++;
        if(stimes[ch] <= times[ch]) cnt ++;
        if(cnt == t.length()) {
            while(start < s.length() && stimes[s.charAt(start)] > times[s.charAt(start)]) {
                stimes[s.charAt(start)] --;
                start ++;
            }
            //
            if(i - start + 1 < len) {
                begin = start;
                end = i;
                len = i - start + 1;
            }
            stimes[s.charAt(start)] --;
            start ++;
            cnt --;
        }
    }
    return begin == -1 ? "" : s.substring(begin, end + 1);
}

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

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

相關(guān)文章

  • leetcode-76-Minimum Window Substring

    摘要：逐步逼近法，類似于牛頓迭代法。重點是找到規(guī)律，然后將規(guī)律加以表示。動態(tài)規(guī)劃，相鄰兩個位置之間的關(guān)系。字符串的疊加，可以增加共性，通過相減可以得到邊界位置處符合規(guī)律的要求。學(xué)會將問題轉(zhuǎn)化為可求的邊界問題。 吃透題目： 任何問題的解決在于理解題目，挖掘本質(zhì)。 這道題目，從一個string中找包含char的最小子序列，O(n)，要求只能遍歷一遍。 每次移動一個index，都嘗試找子序列，通...

    edagarli 評論0 收藏0

  • [LintCode/LeetCode] Minimum Window Substring

    Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

    Corwien 評論0 收藏0

  • [leetcode] Minimum Window Substring

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

    Pines_Cheng 評論0 收藏0

  • [Leetcode] Minimum Window Substring 最小字符串窗口

    摘要：雙指針法復(fù)雜度時間空間思路用一個哈希表記錄目標字符串每個字母的個數(shù)，一個哈希表記錄窗口中每個字母的個數(shù)。先找到第一個有效的窗口，用兩個指針標出它的上界和下界。 Minimum Window Substring Given a string S and a string T, find the minimum window in S which will contain all the...

    Yuanf 評論0 收藏0

  • [LeetCode] 727. Minimum Window Subsequence

    Problem Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W. If there is no such window in S that covers all characters in T, return the empty string...

    kaka 評論0 收藏0

發(fā)表評論

0條評論

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