2023-06-02：给定一个二进制数组 nums 和一个整数 k，
k 位翻转 就是从 nums 中选择一个长度为 k 的 子数组，
同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0。
返回数组中不存在 0 所需的最小 k 位翻转 次数。如果不可能，则返回 -1。
子数组 是数组的 连续 部分。
输入：nums = [0,1,0], K = 1。
输出：2。
答案 2023-06-02：
大体步骤如下：
1.初始化一个大小为 n 的队列 queue，用于存储需要翻转的子数组的起始下标。
2.初始化三个变量 l、r 和 ans 分别为 0，表示当前队列的左端点、右端点和翻转的次数。
3.循环遍历数组 nums 中的每个元素 num：
4.如果队列 queue 长度大于 0 且队列最后一个元素下标加 k 大于数组长度，则返回 -1 表示无法完成翻转；否则，返回翻转次数 ans。
时间复杂度为 O(n)，其中 n 是数组 nums 的长度。循环遍历一次数组 nums，每个元素最多会被加入或弹出队列一次，因此时间复杂度是线性的。
空间复杂度也是 O(n)，因为需要使用一个大小为 n 的队列来存储需要翻转的子数组的下标。同时，由于只保存了子数组的起始下标，因此空间复杂度不会超过 n。需要注意的是，在 C 和 C++ 中，使用指针代替数组时需要手动分配和释放内存，因此还需要额外的空间来存储指向动态分配内存的指针。
go 完整代码如下：
package main
import "fmt"
func minKBitFlips(nums []int, k int) int { n := len(nums) queue := make([]int, n) l, r, ans := 0, 0, 0
for i := 0; i < n; i++ { if l != r && i-queue[l] == k { l++ } if (r-l)%2 == 1 == (nums[i] == 1) { queue[r] = i r++ ans++ } }
if l != r && queue[r-1]+k > n { return -1 } return ans}
func main() { nums := []int{0, 1, 0} k := 1 result := minKBitFlips(nums, k) fmt.Println("Result:", result)}
复制代码
rust 语言完整代码如下：
fn min_k_bit_flips(nums: Vec<i32>, k: i32) -> i32 { let n = nums.len(); let mut queue = vec![0; n]; let (mut l, mut r, mut ans) = (0, 0, 0);
for i in 0..n { if l != r && i - queue[l] == k as usize { l += 1; }
if (r as i32 - l as i32) & 1 == nums[i] { queue[r] = i; r += 1; ans += 1; } }
return if l != r && queue[r - 1] + k as usize > n { -1 } else { ans };}
fn main() { let nums = vec![0, 1, 0]; let k = 1; let result = min_k_bit_flips(nums, k); println!("Result: {}", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>
using namespace std;
int minKBitFlips(vector<int>& nums, int k) { int n = nums.size(); vector<int> queue(n); int l = 0, r = 0, ans = 0; for (int i = 0; i < n; i++) { if (l != r && i - queue[l] == k) { l++; } if (((r - l) & 1) == nums[i]) { queue[r++] = i; ans++; } } return (l != r && queue[r - 1] + k > n) ? -1 : ans;}
int main() { vector<int> nums = { 0, 1, 0 }; int k = 1; int result = minKBitFlips(nums, k); cout << "Result: " << result << endl; return 0;}
复制代码
c 语言完整代码如下：
#include <stdio.h>#include <stdlib.h>
int minKBitFlips(int* nums, int numsSize, int k) { int* queue = (int*)malloc(numsSize * sizeof(int)); int l = 0, r = 0, ans = 0; for (int i = 0; i < numsSize; i++) { if (l != r && i - queue[l] == k) { l++; } if (((r - l) & 1) == nums[i]) { queue[r++] = i; ans++; } } free(queue); return (l != r && queue[r - 1] + k > numsSize) ? -1 : ans;}
int main() { int nums[] = { 0, 1, 0 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int k = 1; int result = minKBitFlips(nums, numsSize, k); printf("Result: %d\n", result); return 0;}
复制代码
评论