2023-06-02：給定一個二進制數組 nums 和一個整數 k，
<bdo id='nexre'></bdo><ul id='nexre'></ul>
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完整代碼如下：
```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語言完整代碼如下：
```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++完整代碼如下：
```cpp
#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語言完整代碼如下：
```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;
}
```
