3192.使二进制数组全部等于 1 的最少操作次数 II

【LetMeFly】3192.使二进制数组全部等于 1 的最少操作次数 II：位运算模拟

力扣题目链接：https://leetcode.cn/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-ii/

给你一个二进制数组 nums 。

你可以对数组执行以下操作 任意 次（也可以 0 次）：

• 选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。

反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。

请你返回将 nums 中所有元素变为 1 的 最少 操作次数。

 

示例 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] 。

示例 2：

输入：nums = [1,0,0,0]

输出：1

解释：
我们可以执行以下操作：

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

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 1

解题方法：位运算模拟

类似于LeetCode 3191.使二进制数组全部等于 1 的最少操作次数 I，本题也从前到后模拟，遇到0则翻转一次即可。

但是不用真的翻转，因为翻转偶数次相当于没有翻转，所以使用一个变量$original$记录是否未翻转即可。

需要翻转 ⇔ (n XOR original)为true

用$n$代表当前元素，$o$代表是否为原始值，则有：

n	o	是否需要翻转
0	0	×
0	1	√
1	0	√
1	1	×

翻转只需要(original XOR= 1)

一旦需要翻转，则original的值需要由0变1或1变0，也就是说original异或一个1即可。

时空复杂度分析

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

/*
01101
10010
11101
11110
11111


n o
0 1 翻
0 0 不
1 1 不
1 0 翻
*/
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0, original = 1;
        for (int t : nums) {
            if (t ^ original) {
                ans++;
                original ^= 1;
            }
        }
        return ans;
    }
};

Go

package main

func minOperations(nums []int) int {
    ans, original := 0, 1
    for _, t := range nums {
        if t ^ original == 1 {
            ans++
            original ^= 1
        }
    }
    return ans
}

Java

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0, original = 1;
        for (int t : nums) {
            if ((t ^ original) == 1) {
                ans++;
                original ^= 1;
            }
        }
        return ans;
    }
}

Python

from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans, original = 0, 1
        for t in nums:
            if t ^ original:
                ans += 1
                original ^= 1
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143066863