20210829 每日总结

• 滑动窗口法练习题

  • # 滑动窗口法模板
    # step1 定义需要维护的变量（通常是最大长度，最小长度，和，哈希表等）
    x, y = ...
    # step2 定义窗口首尾端，根据条件要求，滑动窗口
    start = 0
    for end in range(len):
        # step3 更新需要维护的变量，某些需要if来判断是否更新
        x = new_x
        if condition: y = new_y
        #step 4 - 情况1 题目要求窗口长度固定，用if判断是否达到要求长度
        if 长度达到要求:
        	# 达到长度则左指针向前移动一个格，保证下次右指针移动时长度固定
        	# 移动左指针前，将变量更新
        #step 4 - 情况2 如果窗口长度无特殊要求，一般会涉及窗口内元素是否合法
        # 窗口不合法，用while移动左指针一直到合法为止
        while 不合法：
        	# 更新变量，移动窗口
    return ans
    

  • LC3 无重复字符的最小子串

    • end从头遍历至尾，end遇到字母就加入字典，更新出现频率，当字典长度等于窗口长度时，更新最大长度；当字典长度小于窗口长度时，说明有重复元素，start右移，移动之前将越过的字母频率减1，频率减到0删除该键。

  • LC159 至多包含两个不重复字符的最长子串

    • 不断维护字典 根据字典长度维护maxlen和start位置

  • LC1695 删除子数组的最大得分

    • 其实就是寻找总和最大的连续子数组，同样是利用字典长度和end-start+1来比较

  • LC438 寻找字母异位词

    • 窗口滑动，比较窗口内的字典和给定单词的字典是否相等，窗口长度固定，用if来判断，一旦end位置超限，以后每一轮都是start追着end走。

  • LC209 长度最小子数组

    • 窗口移动的条件是sum > target，因为要求的是最小长度，一旦发现超了，窗口就要缩小了。

  • LC643 子数组的最大平均数

    • end从头遍历至尾，窗口长度为k时更新最大平均值；end移动到大于k时，start往右走，移动之前把总和减掉一个。

  • LC485、487、1004 最大连续1的个数：

    • count+简单的滑动窗口，更新最大长度

  • LC1208 尽可能使字符串相等

    • 滑动窗口计算cost，cost超限之后缩小窗口

  • LC1052 爱生气的书店老板

    • 拆解题意比较重要：需要找到什么时候发动 [不生气] 技能，才能得到最大满意客户量。用固定长度X的窗口遍历，更新因生气而不满意的最大客户量，记录下这个最大窗口出现的起始下标。然后把这个窗口的状态设为0，再计算最大客户量即可

  • LC1423 首尾拿牌可能获得的最大点数

    • 拆解题意：每次从首尾拿一张，拿完会暴露出新的首或尾，不论怎么拿，里面剩下的都是连着的，可以维护一个len-k的滑动窗口，让里面的加和最小，剩下的就是最大的。

  • LC1151 最小交换次数

    • 这种题最关键的是解析题意，找到本质。数一下1的个数，作为滑动窗口的长度，窗口滑动的时候记录里面0的个数，维护一个最小个数，就是需要的交换次数。

  • LC76 最小覆盖子串

    • 两个字典的比较。学习collections.defaultdic 的运用

  • LC1588 所有奇数长度子数组的和

    • 生成一个小于等于数组长度的奇数列表，遍历每一个奇数宽度，对于每一个宽度都用滑动窗口求和即可。

原文：https://www.cnblogs.com/xhmorehair/p/15306667.html