文章目录
1. 题目链接
https://leetcode.cn/problems/minimum-number-of-k-consecutive-bit-flips/description/
2. 题目大意
描述：给定一个仅包含 0 和 1 的数组 numsnums，再给定一个整数 k。
进行一次 k 位翻转包括选择一个长度为 k 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
要求：返回所需的 k 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 −1。
说明：
- 子数组：数组的连续部分。
- 1<=nums.length<=105。
- 1<=k<=nums.length。
3. 示例
输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。
输入：nums = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]
4. 解题思路
每次需要翻转的起始位置肯定是遇到第一个元素为 0 的位置开始反转，如果能够使得整个数组不存在 0，即返回 ans 作为反转次数。
同时我们还可以发现：
- 如果某个元素反转次数为奇数次，元素会由 0→1，1→0。
- 如果某个元素反转次数为偶数次，元素不会发生变化。
每个第 i 位置上的元素只会被前面 [i−k+1,i−1] 的元素影响。所以我们只需要知道前面 k−1 个元素翻转次数的奇偶性就可以了。
同时如果我们知道了前面 k−1 个元素的翻转次数就可以直接修改 nums[i] 了。
我们使用 flip‾count 记录第 i 个元素之前 k−1 个位置总共被反转了多少次，或者 flip‾count是大小为 k−1 的滑动窗口。
- 如果前面第 k−1 个元素翻转了奇数次，则如果 nums[i]==1，则 nums[i] 也被翻转成了 0，需要再翻转 1 次。
- 如果前面第 k−1 个元素翻转了偶数次，则如果 nums[i]==0，则 nums[i] 也被翻转成为了 0，需要再翻转 1 次。
这两句写成判断语句可以写为：if (flip_count + nums[i]) % 2 == 0:。
因为 0<=nums[i]<=1，所以我们可以用 0 和 1 以外的数，比如 2 来标记第 i 个元素发生了翻转，即 nums[i] = 2。这样在遍历到第 i 个元素时，如果有 nums[i−k]==2，则说明 nums[i−k]nums[i−k] 发生了翻转。同时根据 flip‾count 和 nums[i] 来判断第 i 位是否需要进行翻转。
整个算法的具体步骤如下：
- 使用 res 记录最小翻转次数。使用 flip‾count 记录窗口内前 $k - 1 $ 位元素的翻转次数。
- 遍历数组 nums，对于第 i 位元素：
- 如果 i−k>=0，并且 nums[i−k]==2，需要缩小窗口，将翻转次数减一。（此时窗口范围为 [i−k+1,i−1]）。
- 如果 (flip‾count+nums[i])mod2==0，则说明 nums[i] 还需要再翻转一次，将 nums[i] 标记为 2，同时更新窗口内翻转次数 flip‾count 和答案最小翻转次数 ans。
- 遍历完之后，返回 res。
5. 参考代码
class Solution {
public int minKBitFlips(int[] nums, int k) {
int ans = 0;
int flipCount = 0;
for (int i = 0; i < nums.length; i++) {
// 检查是否需要移除窗口外的翻转效果
if (i >= k && nums[i - k] == 2) {
flipCount--;
}
// 如果当前位需要翻转
if ((flipCount + nums[i]) % 2 == 0) {
if (i + k > nums.length) {
return -1; // 无法翻转，返回 -1
}
nums[i] = 2; // 标记翻转
flipCount++;
ans++;
}
}
return ans;
}
}
标签：count,nums,元素,flip,次数,0995,滑动,翻转 From： https://blog.csdn.net/apple_74262176/article/details/144121503