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

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

一般应用场景

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

通用模板

双指针大致逻辑如下:

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


相关文章
|
20天前
|
自然语言处理 Rust 算法
【算法】17. 电话号码的字母组合(多语言实现)
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
【算法】17. 电话号码的字母组合(多语言实现)
|
23天前
|
算法
力扣每日一题 6/23 字符串/模拟
力扣每日一题 6/23 字符串/模拟
13 1
|
23天前
|
索引
力扣每日一题 6/27 字符串 贪心
力扣每日一题 6/27 字符串 贪心
9 0
|
23天前
|
Python
力扣随机一题 模拟+字符串
力扣随机一题 模拟+字符串
9 0
|
3天前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真
|
5天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
7天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
21 7
|
4天前
|
算法
基于粒子群优化的图像融合算法matlab仿真
这是一个基于粒子群优化(PSO)的图像融合算法,旨在将彩色模糊图像与清晰灰度图像融合成彩色清晰图像。在MATLAB2022a中测试,算法通过PSO求解最优融合权值参数,经过多次迭代更新粒子速度和位置,以优化融合效果。核心代码展示了PSO的迭代过程及融合策略。最终,使用加权平均法融合图像,其中权重由PSO计算得出。该算法体现了PSO在图像融合领域的高效性和融合质量。
|
4天前
|
传感器 算法 数据安全/隐私保护
基于鲸鱼优化的DSN弱栅栏覆盖算法matlab仿真
```markdown 探索MATLAB2022a中WOA与DSN弱栅栏覆盖的创新融合,模拟鲸鱼捕食策略解决传感器部署问题。算法结合“搜索”、“包围”、“泡沫网”策略,优化节点位置以最大化复杂环境下的区域覆盖。目标函数涉及能量效率、网络寿命、激活节点数、通信质量及覆盖率。覆盖评估基于覆盖半径比例,旨在最小化未覆盖区域。 ```
|
9天前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现