成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

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

Yuanf / 1514人閱讀

摘要：雙指針法復(fù)雜度時(shí)間空間思路用一個(gè)哈希表記錄目標(biāo)字符串每個(gè)字母的個(gè)數(shù)，一個(gè)哈希表記錄窗口中每個(gè)字母的個(gè)數(shù)。先找到第一個(gè)有效的窗口，用兩個(gè)指針標(biāo)出它的上界和下界。

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".


Note: If there is no such window in S that covers all characters in T, return the emtpy string "".


If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
雙指針法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

用一個(gè)哈希表記錄目標(biāo)字符串每個(gè)字母的個(gè)數(shù)，一個(gè)哈希表記錄窗口中每個(gè)字母的個(gè)數(shù)。先找到第一個(gè)有效的窗口，用兩個(gè)指針標(biāo)出它的上界和下界。然后每次窗口右界向右移時(shí)，將左邊盡可能的右縮，右縮的條件是窗口中字母的個(gè)數(shù)不小于目標(biāo)字符串中字母的個(gè)數(shù)。

注意

用一個(gè)數(shù)組來保存每個(gè)字符出現(xiàn)的次數(shù)，比哈希表容易

保存結(jié)果子串的起始點(diǎn)初值為-1，方便最后判斷是否有正確結(jié)果

代碼 
public class Solution {
    public String minWindow(String S, String T) {
        int[] srcHash = new int[255];
        // 記錄目標(biāo)字符串每個(gè)字母出現(xiàn)次數(shù)
        for(int i = 0; i < T.length(); i++){
            srcHash[T.charAt(i)]++;
        }
        int start = 0,i= 0;
        // 用于記錄窗口內(nèi)每個(gè)字母出現(xiàn)次數(shù) 
        int[] destHash = new int[255];
        int found = 0;
        int begin = -1, end = S.length(), minLength = S.length();
        for(start = i = 0; i < S.length(); i++){
            // 每來一個(gè)字符給它的出現(xiàn)次數(shù)加1
            destHash[S.charAt(i)]++;
            // 如果加1后這個(gè)字符的數(shù)量不超過目標(biāo)串中該字符的數(shù)量，則找到了一個(gè)匹配字符
            if(destHash[S.charAt(i)] <= srcHash[S.charAt(i)]) found++;
            // 如果找到的匹配字符數(shù)等于目標(biāo)串長(zhǎng)度，說明找到了一個(gè)符合要求的子串    
            if(found == T.length()){
                // 將開頭沒用的都跳過，沒用是指該字符出現(xiàn)次數(shù)超過了目標(biāo)串中出現(xiàn)的次數(shù)，并把它們出現(xiàn)次數(shù)都減1
                while(start < i && destHash[S.charAt(start)] > srcHash[S.charAt(start)]){
                    destHash[S.charAt(start)]--;
                    start++;
                }
                // 這時(shí)候start指向該子串開頭的字母，判斷該子串長(zhǎng)度
                if(i - start < minLength){
                    minLength = i - start;
                    begin = start;
                    end = i;
                }
                // 把開頭的這個(gè)匹配字符跳過，并將匹配字符數(shù)減1
                destHash[S.charAt(start)]--;
                found--;
                // 子串起始位置加1，我們開始看下一個(gè)子串了
                start++;
            }
        }
        // 如果begin沒有修改過，返回空
        return begin == -1 ? "" : S.substring(begin,end + 1);
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64475.html

相關(guān)文章

  • [leetcode] Minimum Window Substring

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

    Pines_Cheng 評(píng)論0 收藏0

  • Leetcode[76] Minimum Window Substring

    LeetCode[76] Minimum Window Substring Given a string S and a string T, find the minimum window in S whichwill contain all the characters in T in complexity O(n). For example, S = ADOBECODEBANC T = AB...

    suemi 評(píng)論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 評(píng)論0 收藏0

  • leetcode-76-Minimum Window Substring

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

    edagarli 評(píng)論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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<