995. K 连续位的最小翻转次数
题目来源
思路
方法一、
差分思想
用差分思想来计算当前数字需要翻转的次数。开一个差分数组\(diff[A.length+1]\)来维护，多开1位，减少溢出判断
A的翻转次数为差分数组\(d[i]\)的累加和
当需要翻转时，只改变了\(diff[i]\)和\(diff[i+k]\)的值。故\(diff[i]\)增加1，\(diff[i+k]\)减少1.
对于一个数若其经历了奇数次翻转，则其改变，若经历了偶数次翻转则其值未变，即
- 0翻转偶数次后，数值仍然是0，需要被翻转
- 0翻转奇数次后，数值变为1，无需被翻转
- 1翻转偶数次后，数值任然是1，无需翻转
- 1翻转奇数次后，数值变为0，需要被翻转
class Solution {
public int minKBitFlips(int[] A, int K) {
int len = A.length;
int[] diff = new int[len+1];
int ans = 0, revCnt = 0;
for(int i = 0;i<len;i++){
revCnt += diff[i];
if((A[i]+revCnt) % 2 == 0){
if(i + K > len){
return -1;
}
ans++;
revCnt++;
diff[i+K]--;
}
}
return ans;
}
}
方法二、
滑动窗口
使用队列来模拟滑动窗口，该滑动窗口的含义是前面\(K-1\)个元素中，以哪些位置其实的 子区间 进行了翻转。从左向右滑动，如果当前位置\(i\)需要翻转，则吧该位置存储到队列中。遍历到新位置\(j(j<i+K)\)时，队列中元素的个数代表了\(j\)被前面\(K-1\)个元素翻转的次数。
所以结论que.size() % 2 == A[i]时，当前元素需要翻转。
当\(i+K>N\)时，说明需要翻转大小为\(K\) 的子区间，但是后面剩余的元素不到 \(K\)个了，所以返回 -1。
class Solution {
public int minKBitFlips(int[] A, int K) {
int res = 0;
Deque<Integer> que = new LinkedList<>();
for (int i = 0; i < A.length; i++) {
if (que.size() > 0 && i > que.peek() + K - 1) {
que.removeFirst();
}
//1.本来是1，翻转奇数次变为0，所以需要再次翻转，放入队列
//2.本来是0，翻转偶数次还是0，所以需要再次翻转，放入队列
if (que.size() % 2 == A[i]) {
if (i + K > A.length) return -1;
que.add(i);
res += 1;
}
}
return res;
}
}