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

通用模板

left = 0
right  = 0
while  right < len(s):
# 右指针右移增大窗口
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

|
20天前
|

【算法】17. 电话号码的字母组合（多语言实现）

23 1
|
23天前
|

13 1
|
23天前
|

9 0
|
23天前
|
Python

9 0
|
3天前
|

MCKP-MMF算法是一种启发式流量估计方法，用于寻找无线传感器网络的局部最优解。它从最小配置开始，逐步优化部分解，调整访问点的状态。算法处理访问点的动态影响半径，根据带宽需求调整，以避免拥塞。在MATLAB 2022a中进行了仿真，显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段：慢启动阶段识别瓶颈并重设半径，随后进入周期性调整阶段，追求最大最小公平性。
14 1
|
5天前
|

**摘要：** K-means聚类算法分析，利用MATLAB2022a进行实现。算法基于最小化误差平方和，优点在于简单快速，适合大数据集，但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限，提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值，计算距离代价，寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
24 10
|
7天前
|

21 7
|
4天前
|

7 1
|
4天前
|

markdown 探索MATLAB2022a中WOA与DSN弱栅栏覆盖的创新融合，模拟鲸鱼捕食策略解决传感器部署问题。算法结合“搜索”、“包围”、“泡沫网”策略，优化节点位置以最大化复杂环境下的区域覆盖。目标函数涉及能量效率、网络寿命、激活节点数、通信质量及覆盖率。覆盖评估基于覆盖半径比例，旨在最小化未覆盖区域。 
18 2
|
9天前
|

MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现
14 1