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 所有奇数长度子数组的和
- 生成一个小于等于数组长度的奇数列表，遍历每一个奇数宽度，对于每一个宽度都用滑动窗口求和即可。
-