国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode-76-Minimum Window Substring

edagarli / 1650人閱讀

摘要：逐步逼近法，類似于牛頓迭代法。重點是找到規律，然后將規律加以表示。動態規劃，相鄰兩個位置之間的關系。字符串的疊加，可以增加共性，通過相減可以得到邊界位置處符合規律的要求。學會將問題轉化為可求的邊界問題。

吃透題目：

任何問題的解決在于理解題目，挖掘本質。 
這道題目，從一個string中找包含char的最小子序列，O(n)，要求只能遍歷一遍。
每次移動一個index，都嘗試找子序列，通過對目標子序列統計數目，與當前的char的數目進行合并，然后子循環while的時候，通過減法操作，達到==0的條件時候，就可以知道這是最短的子序列的邊界，同理for循環向后迭代。

相似： kmp算法，保持狀態，省略不必要的遍歷，從上次移動到的位置i，繼續向后移動。

  逐步逼近法，類似于牛頓迭代法。重點是找到規律，然后將規律加以表示。
  動態規劃，相鄰兩個位置之間的關系。

應用：

學會記錄狀態，沒有必要再次重復的位置，通過記錄加以過濾。
字符串的疊加，可以增加共性，通過相減可以得到邊界位置處符合規律的要求。
學會將問題轉化為可求的邊界問題。

import collections

class Solution:
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        missing=len(t)
        need=collections.Counter(t)
        i=I=J=0
        # J=len(s)
        for j,c in enumerate(s,1):
            missing-=need[c]>0
            need[c]-=1
            if not missing:
                # tmp1=s[i]
                # tmp3=need[s[i]]
                # tmp2=need[s[i]] < 0
                while (i=0 and j-i<=J-I) or J==0:
                    I=i
                    J=j
        # print("I,J==>",I,J)
        return s[I:J]

if __name__=="__main__":
    S = "ADOBEBCBODEBBANNNNACB"
    T = "ABC"
    S="ab"
    T="a"
    # S="a"
    # T="aa"
    st=Solution()
    out=st.minWindow(S,T)
    print("out==>",out)

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

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

相關文章

  • 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 評論0 收藏0

  • [leetcode] Minimum Window Substring

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

    Pines_Cheng 評論0 收藏0

  • 實戰項目之自動簡歷

    摘要：自動簡歷項目介紹一個可以自動播放書寫過程簡歷，主要運用原生和的知識點。方法如果展示窗口設置的是或者會自動拉到底部為滾動至底部為滾動至頂部其他參數可選定義緩動動畫，或之一。增加簡歷展示頁編寫增加編寫簡歷內容的展示窗口。 自動簡歷 項目介紹 一個可以自動播放書寫過程簡歷，主要運用原生JS和CSS3的知識點。 用到的庫： prism marked 相關鏈接 預覽點我 源碼點我show...

    Eric 評論0 收藏0

  • 實戰項目之自動簡歷

    摘要：自動簡歷項目介紹一個可以自動播放書寫過程簡歷，主要運用原生和的知識點。方法如果展示窗口設置的是或者會自動拉到底部為滾動至底部為滾動至頂部其他參數可選定義緩動動畫，或之一。增加簡歷展示頁編寫增加編寫簡歷內容的展示窗口。 自動簡歷 項目介紹 一個可以自動播放書寫過程簡歷，主要運用原生JS和CSS3的知識點。 用到的庫： prism marked 相關鏈接 預覽點我 源碼點我show...

    Chao 評論0 收藏0

發表評論

0條評論

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