searchusermenu
  • 发布文章
  • 消息中心
点赞
收藏
评论
分享
原创

2023-06-02:给定一个二进制数组 nums 和一个整数 k, k位翻转 就是从 nums 中

2023-06-03 11:46:58
2
0
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完整代码如下:
 
```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)
}
 
```
 
![在这里插入图片描述](https://img-blog.csdnimg.cn/cd6f4fd5a6d34f6ea66c2c54906962f7.png)
 
# 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);
}
 
```
 
![在这里插入图片描述](https://img-blog.csdnimg.cn/7f4954820dc944a29fbe81c055a2993b.png)
 
# 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;
}
 
```
 
![在这里插入图片描述](https://img-blog.csdnimg.cn/593072db00b9420196379dc16892964c.png)
 
# 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;
}
 
```
 
![在这里插入图片描述](https://img-blog.csdnimg.cn/4c38ab4a1f614a3aaac6050e70944b93.png)

 

0条评论
0 / 1000
3****m
116文章数
2粉丝数
3****m
116 文章 | 2 粉丝
原创

2023-06-02:给定一个二进制数组 nums 和一个整数 k, k位翻转 就是从 nums 中

2023-06-03 11:46:58
2
0
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完整代码如下:
 
```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)
}
 
```
 
![在这里插入图片描述](https://img-blog.csdnimg.cn/cd6f4fd5a6d34f6ea66c2c54906962f7.png)
 
# 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);
}
 
```
 
![在这里插入图片描述](https://img-blog.csdnimg.cn/7f4954820dc944a29fbe81c055a2993b.png)
 
# 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;
}
 
```
 
![在这里插入图片描述](https://img-blog.csdnimg.cn/593072db00b9420196379dc16892964c.png)
 
# 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;
}
 
```
 
![在这里插入图片描述](https://img-blog.csdnimg.cn/4c38ab4a1f614a3aaac6050e70944b93.png)

 

文章来自个人专栏
福大大架构师每日一题
116 文章 | 1 订阅
0条评论
0 / 1000
请输入你的评论
0
0