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：

如果队列 queue 中存在元素，并且当前元素下标减去队列左端点下标等于 k，则说明队列中的第一个元素已经过期，将左端点右移一位。

如果队列 queue 中的元素个数为奇数，并且当前元素与队列最后一个元素不同，则将当前元素下标加入队列尾部，同时将翻转次数 ans 加 1。

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;

}

2023-06-02：给定一个二进制数组 nums 和一个整数 k， k位翻转 就是从 nums 中选择一个长度为 k 的 子数组， 同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1的相关教程结束。