資訊專欄INFORMATION COLUMN
摘要：逐步逼近法，類似于牛頓迭代法。重點是找到規(guī)律，然后將規(guī)律加以表示。動態(tài)規(guī)劃，相鄰兩個位置之間的關(guān)系。字符串的疊加，可以增加共性，通過相減可以得到邊界位置處符合規(guī)律的要求。學會將問題轉(zhuǎn)化為可求的邊界問題。
吃透題目：
任何問題的解決在于理解題目，挖掘本質(zhì)。 這道題目，從一個string中找包含char的最小子序列，O(n)，要求只能遍歷一遍。 每次移動一個index，都嘗試找子序列，通過對目標子序列統(tǒng)計數(shù)目，與當前的char的數(shù)目進行合并，然后子循環(huán)while的時候，通過減法操作，達到==0的條件時候，就可以知道這是最短的子序列的邊界，同理for循環(huán)向后迭代。
相似： kmp算法，保持狀態(tài)，省略不必要的遍歷，從上次移動到的位置i，繼續(xù)向后移動。
逐步逼近法，類似于牛頓迭代法。重點是找到規(guī)律，然后將規(guī)律加以表示。 動態(tài)規(guī)劃，相鄰兩個位置之間的關(guān)系。
應用：
學會記錄狀態(tài)，沒有必要再次重復的位置，通過記錄加以過濾。 字符串的疊加，可以增加共性，通過相減可以得到邊界位置處符合規(guī)律的要求。 學會將問題轉(zhuǎ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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/44744.html
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...
摘要：使用而不是因為我們需要的是最值，中間值我們不在乎，所以一次收斂到最小。下面來三個需要查重并且記錄上次出現(xiàn)的位置，選擇以為例，走到用做檢查，發(fā)現(xiàn)出現(xiàn)過，把移到的下一個。是上個題目的簡易版，或者特殊版。 這里聊一聊解一類問題，就是滿足某一條件的substring最值問題。最開始我們以Minimum Window Substring為例，并整理總結(jié)leetcode里所有類似題目的通解。 Gi...
摘要：自動簡歷項目介紹一個可以自動播放書寫過程簡歷，主要運用原生和的知識點。方法如果展示窗口設置的是或者會自動拉到底部為滾動至底部為滾動至頂部其他參數(shù)可選定義緩動動畫，或之一。增加簡歷展示頁編寫增加編寫簡歷內(nèi)容的展示窗口。 自動簡歷 項目介紹 一個可以自動播放書寫過程簡歷，主要運用原生JS和CSS3的知識點。 用到的庫： prism marked 相關(guān)鏈接 預覽點我 源碼點我show...
摘要：自動簡歷項目介紹一個可以自動播放書寫過程簡歷，主要運用原生和的知識點。方法如果展示窗口設置的是或者會自動拉到底部為滾動至底部為滾動至頂部其他參數(shù)可選定義緩動動畫，或之一。增加簡歷展示頁編寫增加編寫簡歷內(nèi)容的展示窗口。 自動簡歷 項目介紹 一個可以自動播放書寫過程簡歷，主要運用原生JS和CSS3的知識點。 用到的庫： prism marked 相關(guān)鏈接 預覽點我 源碼點我show...
閱讀 3061·2021-11-22 15:29
閱讀 1746·2021-10-12 10:11
閱讀 1786·2021-09-04 16:45
閱讀 2265·2021-08-25 09:39
閱讀 2804·2021-08-18 10:20
閱讀 2532·2021-08-11 11:17
閱讀 458·2019-08-30 12:49
閱讀 3325·2019-08-30 12:49
