題目描述：

在僅包含 0 和 1 的數(shù)組 A 中，一次 K 位翻轉(zhuǎn)包括選擇一個(gè)長(zhǎng)度為 K 的（連續(xù)）子數(shù)組，同時(shí)將子數(shù)組中的每個(gè) 0 更改為 1，而每個(gè) 1 更改為 0。

返回所需的 K 位翻轉(zhuǎn)的最小次數(shù)，以便數(shù)組沒(méi)有值為 0 的元素。如果不可能，返回 -1。

示例 1：

輸入：A = [0,1,0], K = 1
輸出：2
解釋：先翻轉(zhuǎn) A[0]，然后翻轉(zhuǎn) A[2]。

示例 2：

輸入：A = [1,1,0], K = 2
輸出：-1
解釋：無(wú)論我們?cè)鯓臃D(zhuǎn)大小為 2 的子數(shù)組，我們都不能使數(shù)組變?yōu)?[1,1,1]。

示例 3：

輸入：A = [0,0,0,1,0,1,1,0], K = 3
輸出：3
解釋：
翻轉(zhuǎn) A[0],A[1],A[2]: A變成 [1,1,1,1,0,1,1,0]
翻轉(zhuǎn) A[4],A[5],A[6]: A變成 [1,1,1,1,1,0,0,0]
翻轉(zhuǎn) A[5],A[6],A[7]: A變成 [1,1,1,1,1,1,1,1]

思路分析：

題目大意：每次翻轉(zhuǎn)長(zhǎng)度為 K 的子數(shù)組，求最少的翻轉(zhuǎn)次數(shù)使數(shù)組中所有的 0 都更改為 1。如果不能實(shí)現(xiàn)，則返回 -1.

• 結(jié)論 1：后面區(qū)間的翻轉(zhuǎn)，不會(huì)影響前面的元素。因此可以使用貪心策略，從左到右遍歷，遇到每個(gè) 0 都把它和后面的 K 個(gè)數(shù)進(jìn)行翻轉(zhuǎn)。
• 結(jié)論 2：A[i] 翻轉(zhuǎn)偶數(shù)次的結(jié)果是 A[i]；翻轉(zhuǎn)奇數(shù)次的結(jié)果是 A[i] ^ 1。

上面方法超時(shí)的主要原因是我們真實(shí)地進(jìn)行了翻轉(zhuǎn)。根據(jù)結(jié)論二，位置 i 現(xiàn)在的狀態(tài)，和它被前面 K - 1個(gè)元素翻轉(zhuǎn)的次數(shù)（奇偶性）有關(guān)。

我們使用隊(duì)列模擬滑動(dòng)窗口，該滑動(dòng)窗口的含義是前面 K - 1個(gè)元素中，以哪些位置起始的 子區(qū)間進(jìn)行了翻轉(zhuǎn)。該滑動(dòng)窗口從左向右滑動(dòng)，如果當(dāng)前位置 i 需要翻轉(zhuǎn)，則把該位置存儲(chǔ)到隊(duì)列中。遍歷到新位置 j (j < i + K)時(shí)，隊(duì)列中元素的個(gè)數(shù)代表了 i被前面 K - 1個(gè)元素翻轉(zhuǎn)的次數(shù)。

當(dāng) i 位置被翻轉(zhuǎn)了偶數(shù)次，如果 A[i]為 0，那么翻轉(zhuǎn)后仍是 0，當(dāng)前元素需要翻轉(zhuǎn)；
當(dāng) i 位置被翻轉(zhuǎn)了奇數(shù)次，如果 A[i]為 1，那么翻轉(zhuǎn)后是 0，當(dāng)前元素需要翻轉(zhuǎn)。
綜合上面兩點(diǎn)，我們得到一個(gè)結(jié)論，如果 len(que) % 2 == A[i] 時(shí)，當(dāng)前元素需要翻轉(zhuǎn)。

當(dāng) i + K > N 時(shí)，說(shuō)明需要翻轉(zhuǎn)大小為 K 的子區(qū)間，但是后面剩余的元素不到 K 個(gè)了，所以返回 -1。

Python實(shí)現(xiàn)

class Solution(object):
    def minKBitFlips(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        N = len(A)
        que = collections.deque()
        res = 0
        for i in range(N):
            if que and i >= que[0] + K:
                que.popleft()
            if len(que) % 2 == A[i]:
                if i +  K > N: return -1
                que.append(i)
                res += 1
        return res

作者：fuxuemingzhu
鏈接：https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/hua-dong-chuang-kou-shi-ben-ti-zui-rong-z403l/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

java實(shí)現(xiàn)

class Solution {
    public int minKBitFlips(int[] A, int K) {
        int len=A.length;
        int res=0;
        Deque deque=new LinkedList<>();
        for(int i=0;i            if(deque.size()>0 && i>deque.peek()+K-1){
                deque.removeFirst();
            }
            if(deque.size()%2==A[i]){
                if(i+K>len){
                    return -1;
                }
                deque.add(i);
                res=res+1;
            }
        }
        return res;
    }
}