Skip to content

Latest commit

 

History

History

3192.Minimum Operations to Make Binary Array Elements Equal to One II

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
README_EN.md
README_EN.md
 
 
Solution.cpp
Solution.cpp
 
 
Solution.go
Solution.go
 
 
Solution.java
Solution.java
 
 
Solution.py
Solution.py
 
 
Solution.ts
Solution.ts
 
 

README.md

comments difficulty edit_url rating source tags
true
中等
1432
第 133 场双周赛 Q3
贪心
数组
动态规划

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

English Version

题目描述

给你一个二进制数组 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)$。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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

TypeScript

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;
}