K 连续位的最小翻转次数Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给定一个二进制数组 nums 和一个整数 k 。
k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。
返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。
子数组 是数组的 连续 部分。
示例 1：
输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。
示例 2：
输入：nums = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。
示例 3：
输入：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]
提示：
- 1 <= nums.length <= 105
- 1 <= k <= nums.length
# 思路
遍历nums，在i处碰到0，就反转i ~ i + k - 1，如果能变为全1，那么结果就是最少的反转次数
# 解法
class Solution {
public int minKBitFlips(int[] nums, int k) {
int[] d = new int[nums.length + 1];
int re = 0;
int s = 0;
for(int i = 0;i < d.length - 1;i++) {
s += d[i];
boolean t = (s & 1) == 0 ? false : true;
if((!t && nums[i] == 0) || (t && nums[i] == 1)) {
s++;
re++;
if(i + k < d.length) d[i + k]--;
else return -1;
}
}
return re;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 总结
- 分析出几种情况，然后分别对各个情况实现
