【经典LeetCode算法题目专栏分类】【第8期】滑动窗口：最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
《博主简介》
小伙伴们好，我是阿旭。专注于人工智能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题目
- 最小覆盖子串
| 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] |
- 字符串排列
| 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 |
- 找所有字母异位词
| 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 |
- 最长无重复子串
| 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：阿旭算法与机器学习，共同学习交流~
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！