LeetCode 995. K 连续位的最小翻转次数
题目描述
题意分析
每次选择长度恰好为
k的连续区间，把其中所有位取反，求把整个二进制数组变成全1的最少次数；若不存在合法操作方案，返回-1。区间翻转相当于逐位异或，操作顺序不影响最终结果，同一起点翻转两次会完全抵消。因此最优方案中，每个合法起点最多翻转一次，可以按起点从左到右决定是否操作。
解法：强制贪心 + 翻转差分
核心思路
[!blue]
扫描到位置
i时，所有小于i的起点都已经决定，位置0到i - 1也已经修正。尚未决定的起点中，只有i本身能覆盖当前位置，任何更靠右的起点都无法回头修改它。因此当前有效值为0时，必须从i开始翻转；为1时必须不翻，否则后续再也无法把它修正。这个选择是每个可行方案都必须遵守的，不是局部尝试。逐位执行后，若需要翻转时发现
i + k > n，说明唯一能修正当前位置的操作也不合法，任何方案都无解；若顺利走到末尾，每一位都已修正。由于每个起点只执行被迫需要的一次翻转，得到的次数也必然最少。不必真的逐格改写每个长度为
k的窗口。用flip记录覆盖当前位置的已选翻转次数的奇偶性，当前位置的有效值就是nums[i] ^ flip。偶数次翻转等于不变，奇数次翻转等于取反，所以只需维护0或1。从
i开始的翻转覆盖[i, i + k - 1]，到i + k才失效。新增翻转时立即执行flip ^= 1，让后面的扫描看到它的影响，同时登记diff[i + k] ^= 1。每次到达一个位置，先执行flip ^= diff[i]移除恰好到期的影响，再判断当前有效值，避免把已经结束的窗口继续算进去。
解题步骤
- 建立失效标记数组和当前翻转奇偶。
- 扫描每个位置，先撤销到此结束的翻转。
- 有效值为零时，检查剩余长度是否足够放入窗口。
- 足够则计数并立即生效，同时登记失效位置。
i + k == n时窗口恰好到数组末尾，仍然合法；diff分配n + 1个位置，是为了允许登记下标n的失效事件，即使扫描不会再访问它。k == 1时每个原始零各翻一次；数组已经全为一时不会产生操作，答案为零。原数组始终保留原值，所有影响由翻转奇偶表示。
代码实现
class Solution {
public int minKBitFlips(int[] nums, int k) {
int n = nums.length;
// diff[i] 为 1 表示有一次翻转在位置 i 处失效。
int[] diff = new int[n + 1];
// flip 表示当前位置累计被翻转次数的奇偶性。
int flip = 0;
int answer = 0;
for (int i = 0; i < n; i++) {
flip ^= diff[i];
if ((nums[i] ^ flip) == 0) {
// 只有以 i 为起点才能修正位置 i，放不下就无解。
if (i + k > n) {
return -1;
}
answer++;
flip ^= 1;
diff[i + k] ^= 1;
}
}
return answer;
}
}
func minKBitFlips(nums []int, k int) int {
n := len(nums)
// diff[i] 为 1 表示有一次翻转在位置 i 处失效。
diff := make([]int, n+1)
// flip 表示当前位置累计被翻转次数的奇偶性。
flip := 0
answer := 0
for i := 0; i < n; i++ {
flip ^= diff[i]
if (nums[i] ^ flip) == 0 {
// 只有以 i 为起点才能修正位置 i，放不下就无解。
if i+k > n {
return -1
}
answer++
flip ^= 1
diff[i+k] ^= 1
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(n)$，失效标记数组。
关键点总结
[!green]
- 先处理失效事件，再判断当前位置。
- 真实值由原值和生效翻转奇偶共同决定。
- i+k=n 仍是合法窗口，标记数组为这个失效位置留出空间。
易错点总结
[!yellow]
- 只看原数组中的零：此前翻转会改变当前有效值。
- 新增翻转不立即改变 flip：后续位置看不到本次影响。
- 不登记窗口结束：影响错误延续到数组末尾。
- 把恰好到末尾的窗口判为越界：漏掉合法最后起点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1529. 最少的后缀翻转次数 | 中等 | 两题遇到最左错误位时操作都被强制，本题翻固定长度窗口，原题翻整个后缀。 |
| 1109. 航班预订统计 | 中等 | 同样可用起止事件记录区间操作影响，本题只关心当前覆盖的翻转次数奇偶。 |