leetcode995. K 连续位的最小翻转次数

用队列模拟滑动窗口，掌握反转的规律：

1. 当 A[i] 为 0，如果 i 位置被翻转了偶数次，那么翻转后仍是 0，当前元素需要翻转；
2. 当 A[i] 为 1，如果 i 位置被翻转了奇数次，那么翻转后变成 0，当前元素需要翻转。
3. i位置反转的次数等于队列长度
4. 要想满足三，需要维护队列长度，相当于一个窗口（如果r与队列里元素的距离超过k说明前面的反转对后面没有影响了）

def minKBitFlips(nums, k):
    res = 0
    queue = collections.deque()
    for r in range(len(nums)):           #需要反转的元素进入队列
        if queue and queue[0] + k <= r:  #如果r与队列里元素的距离超过k说明前面的反转对后面没有影响了，因为这里包含元素自身，所以等于的时候也弹出来
            queue.popleft()              #如[0,1,1],当r=2时，0位置的反转不会对其产生影响
        if len(queue) % 2 == nums[r]:    #当 A[i] 为 0，如果i位置被翻转了偶数次，那么翻转后仍是0，当前元素需要翻转
            if r + k > len(nums):        #当 A[i]为 1，如果i位置被翻转了奇数次，那么翻转后变成0，当前元素需要翻转。
                return -1                #i位置反转的次数等于队列长度
            res += 1                     #如果需要反转的位置距离末尾长度不足k说明无论如何都无法完成了
            queue.append(r)
    return res
1
2
3
4
5
6
7
8
9
10
11
12