2025-01-22:使二进制数组全部等于 1 的最少操作次数Ⅱ。用go语言,给定一个二进制数组 nums

2025-01-22:使二进制数组全部等于 1 的最少操作次数Ⅱ。用go语言,给定一个二进制数组 nums,你可以对数组进行以下操作任意次(包括0次):

选择任何一个下标 i,并将从该下标开始到数组末尾的所有元素进行反转。反转的意思是将0变为1,或将1变为0。

请计算将 nums 数组中的所有元素都变为1所需的最少操作次数。

1 <= nums.length <= 100000。

0 <= nums[i] <= 1。

输入:nums = [0,1,1,0,1]。

输出:4。

解释:

我们可以执行以下操作:

选择下标 i = 1 执行操作,得到 nums = [0,0,0,1,0] 。

选择下标 i = 0 执行操作,得到 nums = [1,1,1,0,1] 。

选择下标 i = 4 执行操作,得到 nums = [1,1,1,0,0] 。

选择下标 i = 3 执行操作,得到 nums = [1,1,1,1,1] 。

答案2025-01-22:

chatgpt

题目来自leetcode3192。

大体步骤如下:

1.初始数组是 [0, 1, 1, 0, 1],初始操作次数 ops = 0
2.在遍历过程中,根据当前元素和操作次数的奇偶性来决定是否增加操作次数。
3.遍历到第一个元素 0,此时操作次数为偶数,所以需要进行反转,此时数组变为 [1, 1, 1, 0, 1],操作次数加1。
4.继续遍历,下一个元素为 1,此时操作次数为奇数,不需要进行反转,操作次数不变。
5.遍历到下一个元素 1,仍然不需要反转,操作次数不变。
6.下一个元素为 0,操作次数为奇数,需要进行反转,此时数组变为 [1, 1, 1, 1, 0],操作次数加1。
7.最后一个元素是 1,操作次数为偶数,需要进行反转,此时数组变为 [1, 1, 1, 1, 1],操作次数加1。

最终的操作次数为 4,将数组中所有元素变为 1 需要进行 4 次操作。

总的时间复杂度:遍历数组需要 O(n) 的时间复杂度,其中 n 是数组的长度。

总的额外空间复杂度:在解决问题的过程中,只使用了常数级别的额外空间,额外空间复杂度为 O(1)。

Go完整代码如下:

package main

import (
    "fmt"
)

func minOperations(nums []int) int {
    ops := 0
    for _, num := range nums {
        if (num == 0 && ops%2 == 0) || (num == 1 && ops%2 == 1) {
            ops++
        }
    }
    return ops
}

func main() {
    nums := []int{0, 1, 1, 0, 1}
    result := minOperations(nums)
    fmt.Println(result)
}

在这里插入图片描述

Rust完整代码如下:

fn min_operations(nums: Vec<i32>) -> i32 {
    let mut ops = 0;
    for &num in &nums {
        if (num == 0 && ops % 2 == 0) || (num == 1 && ops % 2 == 1) {
            ops += 1;
        }
    }
    ops
}

fn main() {
    let nums = vec![0, 1, 1, 0, 1];
    let result = min_operations(nums);
    println!("{}", result);
}

在这里插入图片描述

python完整代码如下:

# -*-coding:utf-8-*-

def min_operations(nums):
    ops = 0
    for num in nums:
        if (num == 0 and ops % 2 == 0) or (num == 1 and ops % 2 == 1):
            ops += 1
    return ops

if __name__ == "__main__":
    nums = [0, 1, 1, 0, 1]
    result = min_operations(nums)
    print(result)

在这里插入图片描述

solidity完整代码如下:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract MinOperations {
    function minOperations(uint256[] memory nums) public pure returns (uint256) {
        uint256 ops = 0;

        for (uint256 i = 0; i < nums.length; i++) {
            if ((nums[i] == 0 && ops % 2 == 0) || (nums[i] == 1 && ops % 2 == 1)) {
                ops++;
            }
        }

        return ops;
    }
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
488
粉丝
23
喜欢
39
收藏
22
排名:441
访问:2.1 万
私信
所有博文
社区赞助商