class Solution {
public:
int minKBitFlips(vector<int>& nums, int k) {
}
};
995. K 连续位的最小翻转次数
给定一个二进制数组 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 <= 1051 <= k <= nums.length相似题目
原站题解
python3 解法, 执行用时: 1960 ms, 内存消耗: 26 MB, 提交时间: 2023-06-05 10:43:52
class Solution:
def minKBitFlips(self, nums: List[int], k: int) -> int:
n = len(nums)
s = "".join([str(d) for d in nums])
digit = int("0b" + s, 2)
ans = 0
for i in range(n - 1, k - 2, -1):
if not digit & (1 << i):
left = (1 << (i + 1)) - 1
right = (1 << (i - k + 1)) - 1
digit ^= (left - right)
ans += 1
if digit == (1 << n) - 1:
return ans
return -1
python3 解法, 执行用时: 188 ms, 内存消耗: 19.6 MB, 提交时间: 2023-06-05 10:43:35
class Solution:
def minKBitFlips(self, nums: List[int], k: int) -> int:
n = len(nums)
# 使用滚动差分数组进行操作累计数与原始值加和
diff = nums[:]
for i in range(1, n):
diff[i] = nums[i]-nums[i-1]
# 贪心地遍历对每一个当前遇到的0进行k位翻转
pre = 0
ans = 0
for i in range(n-k+1):
pre += diff[i]
# 如果状态为奇数则需要再次进行翻转并影响到往后k个数
if not pre % 2:
pre += 1
ans += 1
if i+k < n:
diff[i+k] -= 1
# 检验剩下的最后k个数是否全为0
for i in range(n-k+1, n):
pre += diff[i]
if not pre % 2:
return -1
return ans
python3 解法, 执行用时: 128 ms, 内存消耗: 21.1 MB, 提交时间: 2023-06-05 10:43:04
class Solution:
def minKBitFlips(self, nums: List[int], k: int) -> int:
n = len(nums)
q = collections.deque()
res = 0
for i in range(n):
if q and i >= q[0] + k:
q.popleft()
if len(q) % 2 == nums[i]:
if i + k > n: return -1
q.append(i)
res += 1
return res
javascript 解法, 执行用时: 92 ms, 内存消耗: 50 MB, 提交时间: 2023-06-05 10:42:06
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minKBitFlips = function(nums, k) {
const n = nums.length;
const diff = new Array(n + 1).fill(0);
let ans = 0, revCnt = 0;
for (let i = 0; i < n; i++) {
revCnt += diff[i];
if ((nums[i] + revCnt) % 2 === 0) {
if ((i + k) > n) {
return -1;
}
++ans;
++revCnt;
--diff[i + k]
}
}
return ans;
};
javascript 解法, 执行用时: 124 ms, 内存消耗: 50.3 MB, 提交时间: 2023-06-05 10:41:44
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minKBitFlips = function(nums, k) {
const n = nums.length;
const diff = new Array(n + 1).fill(0);
let ans = 0, revCnt = 0;
for (let i = 0; i < n; i++) {
revCnt ^= diff[i];
if (nums[i] === revCnt) { // nums[i] ^ revCnt == 0
if ((i + k) > n) {
return -1;
}
++ans;
revCnt ^= 1;
diff[i + k] ^= 1;
}
}
return ans;
};
javascript 解法, 执行用时: 80 ms, 内存消耗: 49.5 MB, 提交时间: 2023-06-05 10:41:23
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minKBitFlips = function(nums, k) {
const n = nums.length;
let ans = 0, revCnt = 0;
for (let i = 0; i < n; ++i) {
if (i >= k && nums[i - k] > 1) {
revCnt ^= 1;
nums[i - k] -= 2; // 复原数组元素，若允许修改数组 nums，则可以省略
}
if (nums[i] == revCnt) {
if (i + k > n) {
return -1;
}
++ans;
revCnt ^= 1;
nums[i] += 2;
}
}
return ans;
};
golang 解法, 执行用时: 160 ms, 内存消耗: 7.4 MB, 提交时间: 2023-06-05 10:41:09
func minKBitFlips(nums []int, k int) (ans int) {
n := len(nums)
revCnt := 0
for i, v := range nums {
if i >= k && nums[i-k] > 1 {
revCnt ^= 1
nums[i-k] -= 2 // 复原数组元素，若允许修改数组 nums，则可以省略
}
if v == revCnt {
if i+k > n {
return -1
}
ans++
revCnt ^= 1
nums[i] += 2
}
}
return
}
golang 解法, 执行用时: 148 ms, 内存消耗: 8.1 MB, 提交时间: 2023-06-05 10:40:58
func minKBitFlips(nums []int, k int) (ans int) {
n := len(nums)
diff := make([]int, n+1)
revCnt := 0
for i, v := range nums {
revCnt ^= diff[i]
if v == revCnt { // v^revCnt == 0
if i+k > n {
return -1
}
ans++
revCnt ^= 1
diff[i+k] ^= 1
}
}
return
}
golang 解法, 执行用时: 108 ms, 内存消耗: 8.1 MB, 提交时间: 2023-06-05 10:40:46
func minKBitFlips(nums []int, k int) (ans int) {
n := len(nums)
diff := make([]int, n+1)
revCnt := 0
for i, v := range nums {
revCnt += diff[i]
if (v+revCnt)%2 == 0 {
if i+k > n {
return -1
}
ans++
revCnt++
diff[i+k]--
}
}
return
}
java 解法, 执行用时: 5 ms, 内存消耗: 52.7 MB, 提交时间: 2023-06-05 10:40:30
// 差分数组
class Solution {
public int minKBitFlips(int[] nums, int k) {
int n = nums.length;
int[] diff = new int[n + 1];
int ans = 0, revCnt = 0;
for (int i = 0; i < n; ++i) {
revCnt += diff[i];
if ((nums[i] + revCnt) % 2 == 0) {
if (i + k > n) {
return -1;
}
++ans;
++revCnt;
--diff[i + k];
}
}
return ans;
}
}
java 解法, 执行用时: 3 ms, 内存消耗: 53 MB, 提交时间: 2023-06-05 10:40:17
// 差分数组
class Solution {
public int minKBitFlips(int[] nums, int k) {
int n = nums.length;
int[] diff = new int[n + 1];
int ans = 0, revCnt = 0;
for (int i = 0; i < n; ++i) {
revCnt ^= diff[i];
if (nums[i] == revCnt) { // nums[i] ^ revCnt == 0
if (i + k > n) {
return -1;
}
++ans;
revCnt ^= 1;
diff[i + k] ^= 1;
}
}
return ans;
}
}
java 解法, 执行用时: 4 ms, 内存消耗: 57.1 MB, 提交时间: 2023-06-05 10:39:59
// 滑动窗口
class Solution {
public int minKBitFlips(int[] nums, int k) {
int n = nums.length;
int ans = 0, revCnt = 0;
for (int i = 0; i < n; ++i) {
if (i >= k && nums[i - k] > 1) {
revCnt ^= 1;
nums[i - k] -= 2; // 复原数组元素，若允许修改数组 nums，则可以省略
}
if (nums[i] == revCnt) {
if (i + k > n) {
return -1;
}
++ans;
revCnt ^= 1;
nums[i] += 2;
}
}
return ans;
}
}
cpp 解法, 执行用时: 100 ms, 内存消耗: 103.6 MB, 提交时间: 2023-06-05 10:39:41
// 滑动窗口
class Solution {
public:
int minKBitFlips(vector<int>& nums, int k) {
int n = nums.size();
int ans = 0, revCnt = 0;
for (int i = 0; i < n; ++i) {
if (i >= k && nums[i - k] > 1) {
revCnt ^= 1;
nums[i - k] -= 2; // 复原数组元素，若允许修改数组 nums，则可以省略
}
if (nums[i] == revCnt) {
if (i + k > n) {
return -1;
}
++ans;
revCnt ^= 1;
nums[i] += 2;
}
}
return ans;
}
};
cpp 解法, 执行用时: 156 ms, 内存消耗: 108.3 MB, 提交时间: 2023-06-05 10:39:24
class Solution {
public:
int minKBitFlips(vector<int>& nums, int k) {
int n = nums.size();
vector<int> diff(n + 1);
int ans = 0, revCnt = 0;
for (int i = 0; i < n; ++i) {
revCnt ^= diff[i];
if (nums[i] == revCnt) { // nums[i] ^ revCnt == 0
if (i + k > n) {
return -1;
}
++ans;
revCnt ^= 1;
diff[i + k] ^= 1;
}
}
return ans;
}
};
cpp 解法, 执行用时: 124 ms, 内存消耗: 108.3 MB, 提交时间: 2023-06-05 10:39:15
// 差分数组
class Solution {
public:
int minKBitFlips(vector<int>& nums, int k) {
int n = nums.size();
vector<int> diff(n + 1);
int ans = 0, revCnt = 0;
for (int i = 0; i < n; ++i) {
revCnt += diff[i];
if ((nums[i] + revCnt) % 2 == 0) {
if (i + k > n) {
return -1;
}
++ans;
++revCnt;
--diff[i + k];
}
}
return ans;
}
};