题目描述

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

Example 1:

Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].

Example 2:

Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].

Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

Note:

1. 1 <= A.length <= 30000
2. 1 <= K <= A.length

题意：在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。返回所需的 K 位翻转的次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

算法1

(队列实现滑动窗口) $O(n)$

题解：首先我们可以知道，对于每个位置而言，只有初始状态和总共被反转了多少次决定了自己最终的状态。另一方面，我们知道每一个长度为K的区间，最多只会被反转一次，因为两次反转后对最终结果没有影响。基于此，我们从前往后遍历数组，如果遇到一个0，我们将当前位置开始的长度为k区间的区间反转。如果遇到0时，剩下的区间长度不足K说明我们没有办法完成反转。但是如果我们每次反转当前区间时，将区间内每个数都取反，时间复杂度是$O(n*k)$的，这样是不够快的。因为我们需要优化一下，我们再考虑每个位置上的元素，他只会被前面K - 1个元素是否被反转所影响，所以我们只需要知道前面k - 1个元素总共反转了多少次(更进一步的说我们只关系反转次数的奇偶性)。

我们使用一个队列保存i前面k - 1个位置有多少元素被反转了。

如果队列长度为奇数，那么当前位置的1被变成0了需要反转，如果为偶数，说明当前位置的0还是0，需要反转。

如果最后k - 1个位置还有0的话说明失败。否则将i加入队列，更新答案。

时间复杂度：每个元素最多被进入队列和出队列一次，所以总的时间复杂度为$O(n)$的。

    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size(),res = 0;
        queue<int> q;
        for(int i = 0 ; i < n; i ++)
        {
            while(!q.empty() && q.front() + K <= i)
                q.pop();
            if(A[i] == q.size() % 2)
            {
                if(i + K > n) return -1;
                q.push(i);
                res ++;
            }
        }
        return res;
    }