Comment on page
995.Minimum-Number-of-K-Consecutive-Bit-Flips
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]
Flip ^0 = flip
Flip ^1 = ~flip
class Solution {
public int minKBitFlips(int[] A, int K) {
int N = A.length;
int[] hint = new int[N];
int ans = 0, flip = 0;
for (int i = 0; i < N; i++) {
flip ^= hint[i]; // first 0^0 = 0
if (A[i] == flip) {
ans++;
if (i + K > N) {
return -1;
}
flip ^= 1; // 0^1 = 1, 1^1 = 0
if (i + K < N) {
hint[i + K] ^= 1;
}
}
}
return ans;
}
}
解法，贪心 证明： 如果第一个是0， 它别无选择，只能带动右边的K-1个一起转奇数次。（因为求最小，我们只转一次） 如果第一个是1， 它别无选择，只能带动右边的K-1个一起转偶数次。（因为求最小， 我们转 0次） 现在第一个搞定了， 下面解决 N - 1的子问题。
但不管怎么样，请不要动前面已经处理好的。万一你动了，你还得动回来，不折腾。
public int minKBitFlips(int[] A, int K) {
int count = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] == 1) continue;
if (i + K - 1 < A.length) {
for (int j = 0; j < K; j++) {
A[i + j] = 1 - A[i + j];
}
count++;
} else {
return -1;
}
}
return count;
}