Leecode #995. K 连续位的最小翻转次数

在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。

返回所需的 K 位翻转的次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

示例

示例 1：

输入：A = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。
示例 2：

输入：A = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。
示例 3：

输入：A = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

解题思路

​ 拿到题没有什么思路，第一个想法就是遍历数组，然后遇到0就翻转并保留最近一位0的位置，到尾端的时候判断是否满足条件。这样的算法很好完成，结果是超时~官方给的思路其实也是如此，但是设置了很巧妙的hint来避免翻转时浪费的时间，具体算法如下

我们设置初始化一个变量flip status=0来表示当前数组是否被翻转，如果flip status=1，那么我们就将值为1的元素视为0，即if filp status == A[i] then FILP。

需要注意的是，我们只翻转了K个元素，这K个元素上filp statsu为1没错，但是K+1这个元素上的filp status依旧为0！因此我们需要另外一个变量hint来提醒我们恢复翻转状态，具体代码如下：

class Solution:
    def minKBitFlips(self, A, K) -> int:
        from collections import defaultdict
        l = len(A)
        hint = defaultdict(int)
        count = filp_status = 0
        for i in range(l):
            filp_status = filp_status != hint.get(i, 0) # refresh filp status
            if filp_status == A[i]: # if [filp=0 & item=0] or [filp=1 & item=1] -> need to flip
                if i+K>l: return -1
                count += 1
                filp_status = 1 - filp_status # change filp status
                if i+K<l: hint[i+K] = 1 # indicate that when pointer goes to [i+K], we need filp back!
        return count