跳转至

3192. 使二进制数组全部等于 1 的最少操作次数 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

解法

方法一：位运算

我们注意到，每当我们将某个位置的元素变为 1 时，它的右侧的所有元素都会被反转。因此，我们可以用一个变量 $v$ 来记录当前位置及其右侧的元素是否被反转，如果被反转，那么 $v$ 的值为 1，否则为 0。

我们遍历数组 $\textit{nums}$，对于每个元素 $x$，我们将 $x$ 与 $v$ 进行异或运算，如果 $x$ 为 0，那么我们需要将 $x$ 变为 1，我们需要进行反转操作，我们将答案加一，并将 $v$ 取反。

遍历结束后，我们就可以得到最少操作次数。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

1
2
3
4
5
6
7
8
9
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = v = 0
        for x in nums:
            x ^= v
            if x == 0:
                ans += 1
                v ^= 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int minOperations(int[] nums) {
        int ans = 0, v = 0;
        for (int x : nums) {
            x ^= v;
            if (x == 0) {
                v ^= 1;
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0, v = 0;
        for (int x : nums) {
            x ^= v;
            if (x == 0) {
                v ^= 1;
                ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minOperations(nums []int) (ans int) {
    v := 0
    for _, x := range nums {
        x ^= v
        if x == 0 {
            v ^= 1
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function minOperations(nums: number[]): number {
    let [ans, v] = [0, 0];
    for (let x of nums) {
        x ^= v;
        if (x === 0) {
            v ^= 1;
            ++ans;
        }
    }
    return ans;
}

评论