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

資訊專欄INFORMATION COLUMN

leetcode-76-Minimum Window Substring

edagarli / 1716人閱讀

摘要：逐步逼近法，類似于牛頓迭代法。重點(diǎn)是找到規(guī)律，然后將規(guī)律加以表示。動(dòng)態(tài)規(guī)劃，相鄰兩個(gè)位置之間的關(guān)系。字符串的疊加，可以增加共性，通過(guò)相減可以得到邊界位置處符合規(guī)律的要求。學(xué)會(huì)將問(wèn)題轉(zhuǎn)化為可求的邊界問(wèn)題。

吃透題目：

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

相似： kmp算法，保持狀態(tài)，省略不必要的遍歷，從上次移動(dòng)到的位置i，繼續(xù)向后移動(dòng)。

  逐步逼近法，類似于牛頓迭代法。重點(diǎn)是找到規(guī)律，然后將規(guī)律加以表示。
  動(dòng)態(tài)規(guī)劃，相鄰兩個(gè)位置之間的關(guān)系。

應(yīng)用：

學(xué)會(huì)記錄狀態(tài)，沒(méi)有必要再次重復(fù)的位置，通過(guò)記錄加以過(guò)濾。
字符串的疊加，可以增加共性，通過(guò)相減可以得到邊界位置處符合規(guī)律的要求。
學(xué)會(huì)將問(wèn)題轉(zhuǎn)化為可求的邊界問(wèn)題。

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)

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

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

相關(guān)文章

  • 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

  • [leetcode] Minimum Window Substring

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

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

  • 實(shí)戰(zhàn)項(xiàng)目之自動(dòng)簡(jiǎn)歷

    摘要：自動(dòng)簡(jiǎn)歷項(xiàng)目介紹一個(gè)可以自動(dòng)播放書(shū)寫過(guò)程簡(jiǎn)歷，主要運(yùn)用原生和的知識(shí)點(diǎn)。方法如果展示窗口設(shè)置的是或者會(huì)自動(dòng)拉到底部為滾動(dòng)至底部為滾動(dòng)至頂部其他參數(shù)可選定義緩動(dòng)動(dòng)畫(huà)，或之一。增加簡(jiǎn)歷展示頁(yè)編寫增加編寫簡(jiǎn)歷內(nèi)容的展示窗口。 自動(dòng)簡(jiǎn)歷 項(xiàng)目介紹 一個(gè)可以自動(dòng)播放書(shū)寫過(guò)程簡(jiǎn)歷，主要運(yùn)用原生JS和CSS3的知識(shí)點(diǎn)。 用到的庫(kù)： prism marked 相關(guān)鏈接 預(yù)覽點(diǎn)我 源碼點(diǎn)我show...

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

  • 實(shí)戰(zhàn)項(xiàng)目之自動(dòng)簡(jiǎn)歷

    摘要：自動(dòng)簡(jiǎn)歷項(xiàng)目介紹一個(gè)可以自動(dòng)播放書(shū)寫過(guò)程簡(jiǎn)歷，主要運(yùn)用原生和的知識(shí)點(diǎn)。方法如果展示窗口設(shè)置的是或者會(huì)自動(dòng)拉到底部為滾動(dòng)至底部為滾動(dòng)至頂部其他參數(shù)可選定義緩動(dòng)動(dòng)畫(huà)，或之一。增加簡(jiǎn)歷展示頁(yè)編寫增加編寫簡(jiǎn)歷內(nèi)容的展示窗口。 自動(dòng)簡(jiǎn)歷 項(xiàng)目介紹 一個(gè)可以自動(dòng)播放書(shū)寫過(guò)程簡(jiǎn)歷，主要運(yùn)用原生JS和CSS3的知識(shí)點(diǎn)。 用到的庫(kù)： prism marked 相關(guān)鏈接 預(yù)覽點(diǎn)我 源碼點(diǎn)我show...

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

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

0條評(píng)論

閱讀需要支付1元查看
<