python 刷题框架之滑动窗口
刷题框架系列-滑动窗口
有点久没写了,最近一直在刷题找工作,看到了一个大佬总结的各种算法题的解题框架,只是原始版本是C++,看着有点费劲,又觉得很有必要记录下来,方便查阅,写成python版,保存在这边.下面直接上代码 滑动窗口主要用来解决链表,字串,数组问题.
# 滑动窗口算法框架
def slidingWindow(s:str, t:str):
# need 记录需要的字符数量. window记录窗口里面相应字符的数量.
need = {
}
window = {
}
for i in t:
need[i] = need.get(i, 0) + 1
left = right = 0
valid = 0
while (right < len(s)):
# c 是将移入窗口的字符
c = s[right]
# 右移窗口
right += 1
# 进行窗口内数据的一系列更新
...
# ----debug 输出的位置----
print(Window:[%d, %d]
, %(left, right)
# -----------------------
# 判断左侧窗口是否需要收缩
while (window needs shrink):
# d 是将要移出窗口的字符
d = s[left]
# 右移窗口
left += 1
# 进行窗口内数据的一系列更新
...
例题:leetcode 76:最小覆盖子串
下一篇：
时间复杂度与空间复杂度