Leetcode刷题——滑动窗口

滑动窗口算法框架

扩大窗口:寻找可行解

缩小窗口:找到最优解

def slidingWindows(s,t): # source, target
    need = collections.Counter(t) # 需要出现的次数
    windows = dict.fromkeys(need.keys(),0) # 窗口中出现的次数
    left = right = 0 # 左右指针表示窗口[left,right)
    valid = 0 # 表示窗口中满足need条件的字符个数
    while right < len(s):
        c = s[right] # 移入窗口的字符
        right += 1
        
        # 窗口内数据的更新
        if c in need:
            windows[c] += 1
            if windows[c] == need[c]:
                valid += 1
                
        print(letf,right) # debug输出位置
        
        while shrink: # 左窗口需要收缩
            d = s[left] # 移出窗口的字符
            left += 1
            
            # 窗口内数据的更新 
            if d in need:
                if windows[d] == need[d]:
                    valid -= 1
                    windows[d] -= 1

思考四个问题:

1、当移动 right 扩大窗口,即加入字符时,应该更新哪些数据?

2、什么条件下,窗口应该暂停扩大,开始移动 left 缩小窗口?

3、当移动 left 缩小窗口,即移出字符时,应该更新哪些数据?

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?

最小覆盖子串(困难)

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.Counter(t)
        windows = dict.fromkeys(need.keys(),0)
        left = right = 0
        valid = 0 # 满足need的个数
        minstr = s + 'A'
        while right < len(s):
            c = s[right]
            right += 1
​
            # 窗口内数据更新
            if c in need:
                windows[c] += 1
                if windows[c] == need[c]:
                    valid += 1
            
            while valid >= len(need): # 收缩窗口
                minstr = s[left:right] if len(s[left:right]) < len(minstr) else minstr
                d = s[left] # 移出字符
                left += 1
​
                # 窗口内数据更新
                if d in need:
                    if windows[d] == need[d]:
                        valid -= 1
                    windows[d] -= 1
        if minstr == s + 'A': return ""
        return minstr

发表评论