【滑动窗口-1004. 最大连续1的个数 III】
题目描述
1004. 最大连续1的个数 III
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
分析
首先将1的下标存到列表lst中，我们想要维护一个区间，区间的左端点为01串中的一个1，右端点也是01串中的一个1,即两个端点值为lst中的元素。
合法的区间为：这两个端点之间的0的个数小于等于k，那么当前合法区间所构成的连续1的个数为 ：区间中1的个数+k
当区间不合法时，被动移动左端点到下一个1的位置，区间合法时右端点移到到下一个1的位置
代码
def ans(s: list[int], k: int) -> int: n = len(s) lst = [i for i in range(len(s)) if s[i] == 1]# 1的个数为0if len(lst) == 0:return min(n,k)# 0的个数小于等于kif n-len(lst) <= k:return nl = 0max_len = 0for r in range(len(lst)):# 要保证合法区间s[l],s[r] 之间0的个数小于等于kwhile (lst[r] - lst[l]) - (r - l) > k:l += 1# 1的个数+kmax_len = max(max_len, r-l+1+k)return max_len扩展
这份代码同样使用当01串变为有颜色的珠子：
问题描述：有长度为n的带颜色的珠子，有m 种颜色，可以随机将k个珠子变成任意颜色，问变完后，连续相同颜色的珠子的长度
分析：将每种颜色的下标分别存到相应的字典中，对于每个字典就转化成了上面的01串问题，因为要遍历的是字典中的每个元素（对应于s中每种颜色的下标），所以将每种颜色的字典中的元素都遍历完，总共遍历n次，故均摊复杂度依然是O(n)
# 对有颜色的01串操作k次（改变任意字符的颜色）后，最长连续颜色的子串长度，m种颜色# 多跳滑动窗口，保证窗口中操作次数小于等于Kdef ans(self, s: list[int], k: int) -> int: n = len(s)from collections import defaultdictdic = defaultdict(list)for i in range(n):dic[s[i]].append(i) max_len = 0 for key, lst in dic.items(): # 0的个数小于等于kif n-len(lst) <= k:return nl = 0for r in range(len(lst)):while (s[r]-s[l]) -(r-l) > k :l += 1max_len = max(max_len, r-1+1 +k )return max_len
太简洁了！感谢四老师！