995. Minimum Number of K Consecutive Bit Flips -----H

 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

A:

        // seems that this is a greedy method, 反正左边首先发现的0 是必须要翻一下的。

从左往右，每次看到一个0， 就翻过来

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        // seems that this is a greedy method, 
        //whenever find 0 , we need flip at it at least once
        int count =0;
        int n = A.size();
        for(int i =0;i<= n-K; i++ ){
            if(A[i]==1){
                continue;
            }
            count++;
            for(int j = i;j<i+K;j++){
                A[j] = 1-A[j];
            }
        }
        for(int i = n-K+1;i<n;i++){
            if(A[i]==0){
                return -1;
            }
        }
        return count;
    }
};

然而超时了， 反正外边的for 不能动。  就只能修改inner for loop. 

可以记录每个位置被反转了的次数。  然而我们又不想遍历所有的 K 个值，那么我们保留其最右边的index， i + K 

use deque to record all added flipped size.   And Pop when we have finished visiting 

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        // greedy method, whenever find 0(or was flipped to 0), we flip at it
        int count =0;
        int n = A.size();
        deque<int> dq;
        for(int i =0;i<= n-K; i++ ){
            if((A[i] + dq.size())%2==0){
                count++;
                dq.push_back(i+K-1);// INCLUSIVE, need -1
            }
            if(not dq.empty() && dq.front() <= i){
                dq.pop_front();
            }
        }
        for(int i = n-K+1;i<n;i++){
            if((A[i] + dq.size())%2==0 ){
                return -1;
            }
            if(not dq.empty() && i == dq.front()){ // MUST NEED
                dq.pop_front();
            }
        }
        return count;
    }
};

Mistakes:

1: dq.push_back(i+K-1);// INCLUSIVE, need -1  

2:  最后的尾巴，没有用 dq.pop_front()    哎，  SB了。 真正的面试，又挂了