LeetCode如何解決重塑矩陣問題

題目描述：

在僅包含 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]

思路分析：

題目大意：每次翻轉長度為 K 的子數組，求最少的翻轉次數使數組中所有的 0 都更改為 1。如果不能實現，則返回 -1.

• 結論 1：后面區間的翻轉，不會影響前面的元素。因此可以使用貪心策略，從左到右遍歷，遇到每個 0 都把它和后面的 K 個數進行翻轉。
• 結論 2：A[i] 翻轉偶數次的結果是 A[i]；翻轉奇數次的結果是 A[i] ^ 1。

上面方法超時的主要原因是我們真實地進行了翻轉。根據結論二，位置 i 現在的狀態，和它被前面 K - 1個元素翻轉的次數（奇偶性）有關。

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

當 i 位置被翻轉了偶數次，如果 A[i]為 0，那么翻轉后仍是 0，當前元素需要翻轉；
當 i 位置被翻轉了奇數次，如果 A[i]為 1，那么翻轉后是 0，當前元素需要翻轉。
綜合上面兩點，我們得到一個結論，如果 len(que) % 2 == A[i] 時，當前元素需要翻轉。

當 i + K > N 時，說明需要翻轉大小為 K 的子區間，但是后面剩余的元素不到 K 個了，所以返回 -1。

Python實現

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/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

java實現

class Solution {
    public int minKBitFlips(int[] A, int K) {
        int len=A.length;
        int res=0;
        Deque<Integer> deque=new LinkedList<>();
        for(int i=0;i<len;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;
    }
}