题目描述
朴素法
class Solution {
public int minKBitFlips(int[] A, int K) {
int count = 0;
for(int i = 0; i+K <= A.length; ++i) {
if(A[i] == 0) {
count++;
flip(A, i, K);
}
}
boolean valid = true;
for(int i = 0; i < A.length; ++i) {
if(A[i] == 0) {
return -1;
}
}
return count;
}
void flip(int[] a, int from, int k) {
for(int i = from; i < from+k; ++i) {
a[i] = 1-a[i];
}
}
}
差分(推荐)
class Solution {
public int minKBitFlips(int[] A, int k) {
int n = A.length;
int[] diff = new int[n + 1];
int cnt = 0, ret = 0;
for(int i = 0; i < n; i++) {
cnt += diff[i];
if((A[i] + cnt) % 2 == 0) {
diff[i + 1] += 1;
if(i + k <= n) diff[i + k] -= 1;
else return -1;
ret++;
}
}
return ret;
}
}
滑动窗口(推荐)
class Solution {
public int minKBitFlips(int[] A, int k) {
int n = A.length;
Queue<Integer> queue = new LinkedList<>();
int ret = 0;
for(int i = 0; i < n; i++) {
while(!queue.isEmpty() && queue.peek() + k <= i) queue.poll();
if((queue.size() + A[i]) % 2 == 0) {
ret++;
queue.offer(i);
if(i + k > A.length) return -1;
}
}
return ret;
}
}
差分数组的解法可以再详细写下说明吗, 差分数组不是下标从1开始的吗, 第0个元素有意义么
这里实质就是求前面有多少个flip影响了当前位置。差分操作:若想将数组a[L~R]全部加上c 等价于在其差分数组上进行一下操作b[L] += c, b[R + 1] -= c. 所以差分数组长度是n + 1