【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串

2023-12-23 00:11:56

《博主简介》

小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。
?更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~
👍感谢小伙伴们点赞、关注!

《------往期经典推荐------》

一、AI应用软件开发实战专栏【链接】
二、机器学习实战专栏【链接】,已更新31期,欢迎关注,持续更新中~~
三、深度学习【Pytorch】专栏【链接】
四、【Stable Diffusion绘画系列】专栏【链接】

一般应用场景

数组,字符串子串等问题。

通用模板

双指针大致逻辑如下:

left =?0

right ?=?0

while??right <?len(s):

????# 右指针右移增大窗口

????window.add(s[right])

????right ?+=?1

????while?isvalid:

????????# 当满足某种条件时开始从左边收缩窗口

????????window.remove(s[left])

????????left +=?1

代码模板:

def?slidingWindow(s,?t):

????from?collections import?defaultdict

????# defaultdict(int)对于不存在的键默认值为0,

????# 可以直接进行window[c] += 1的操作,免去了判断过程

????window =?defaultdict(int)

????needs??=?defaultdict(int)

????left =?0

????right =?0

????for?c in?t:

????????needs[c]?+=?1

????while?right <?len(s):

????????# c1为移入窗口的字符

????????c1 =?s[right]

????????# 窗口右移

????????right +=?1

????????# 进行窗口内数据的相关操作

????????# TODO

????????# 判断左侧窗口是否要收缩

????????while?window needs shrink:

????????????# c2为将要移出窗口的字符

????????????c2 =?s[left]

????????????# 左指针右移,收缩窗口

????????????left +=?1

????????????# 进行窗口内数据的相关操作

????????????# TODO

相关Leetcode题目

  1. 最小覆盖子串

class?Solution:

????def?minWindow(self,?s:?str,?t:?str)?->?str:

????????from?collections import?defaultdict

????????needs =?defaultdict(int)

????????window =?defaultdict(int)

????????left =?0

????????right =?0

????????count =?0?#window中满足条件的字符数

????????start =?0 #记录最小子串的起始位置

????????min_len =?float('inf') #记录最小子串的长度

????????for?c in?t:

????????????needs[c]?+=?1

????????while?right <?len(s):

????????????c1 =?s[right]

????????????right +=?1

????????????if??c1 in?needs:

????????????????window[c1]?+=?1

????????????????if?window[c1]?==?needs[c1]:

????????????????????count +=?1

????????????while?count ==?len(needs):

????????????????# 更新最小覆盖子串

????????????????if?right -?left <?min_len:

????????????????????start =?left

????????????????????min_len =?right -?left

????????????????c2 =?s[left]

????????????????left +=?1

????????????????if?c2 in?needs:

????????????????????window[c2]?-=?1

????????????????????if?window[c2]?<?needs[c2]:

????????????????????????count -=?1

????????if?min_len ==?float('inf'):

????????????return?''

????????else:

????????????return?s[start:start+min_len]

  1. 字符串排列

class?Solution:

????def?checkInclusion(self,?s1:?str,?s2:?str)?->?bool:

????????from?collections ?import?defaultdict

????????needs =?defaultdict(int)

????????for?c in?s1:

????????????needs[c]?+=?1

????????window =?defaultdict(int)

????????left =?0

????????right =?0

????????count =?0

????????while?right <?len(s2):

????????????c1 =?s2[right]

????????????right +=?1

????????????if?c1 in?needs:

????????????????window[c1]?+=?1

????????????????if?window[c1]?==?needs[c1]:

????????????????????count +=?1

????????????while?count ==?len(needs):

????????????????if?right -?left ==?len(s1):

????????????????????# 如果子串长度与s1相等则包含

????????????????????return?True

????????????????c2 =?s2[left]

????????????????if?c2 in?needs:

????????????????????window[c2]?-=?1

????????????????????if?window[c2]?<?needs[c2]:

????????????????????????count -=?1

????????????????left +=?1

????????return?False

  1. 找所有字母异位词

class?Solution:

????def?findAnagrams(self,?s:?str,?p:?str)?->?List[int]:

????????from?collections import?defaultdict

????????needs =?defaultdict(int)

????????window =?defaultdict(int)

????????left =?0

????????right =?0

????????count =?0

????????res =?[]

????????for?c in?p:

????????????needs[c]?+=?1

????????while?right <?len(s):

????????????c1 =?s[right]

????????????if?c1 in?needs:

????????????????window[c1]?+=?1

????????????????if?window[c1]?==?needs[c1]:

????????????????????count +=?1

????????????right +=?1

????????????while?count ==?len(needs):

????????????????if?right -?left ==?len(p):

????????????????????res.append(left)

????????????????c2 =?s[left]

????????????????if?c2 in?needs:

????????????????????window[c2]?-=?1

????????????????????if?window[c2]?<?needs[c2]:

????????????????????????count -=?1

????????????????left +=?1

????????return?res

  1. 最长无重复子串

class?Solution:

????def?lengthOfLongestSubstring(self,?s:?str)?->?int:

????????max_len =?0

????????left =?0

????????right =?0

????????n =?len(s)

????????from?collections import?defaultdict

????????window =?defaultdict(int)

????????while?right <?n:

????????????c1 =?s[right]

????????????right +=?1

????????????window[c1]?+=?1

????????????while?window[c1]?>?1:

????????????????c2 =?s[left]

????????????????left +=?1

????????????????window[c2]?-=?1

????????????max_len =?max(max_len,?right -?left)

????????return?max_len

关于本篇文章大家有任何建议或意见,欢迎在评论区留言交流!

觉得不错的小伙伴,感谢点赞、关注加收藏哦!

欢迎关注下方GZH:阿旭算法与机器学习,共同学习交流~

文章来源:https://blog.csdn.net/qq_42589613/article/details/135162153
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。