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

2024-10-19

题目:

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

思路:

思路和昨天的题目非常像
对于 nums[0] 来说,if nums[0] == 0,那么只有翻转它才能所有元素变为 1 的可能
我们记录当考虑 nums[i] 时,前面操作了多少次:
	如果是奇数次,那么 nums[i] 需要翻转
	如果是偶数次,那么就不需要翻转
将 nums[i] 改变后,再去判断是否需要翻转,一直到数组末尾即可

代码:

class Solution {
public:
    int minOperations(vector<int>& nums) {
        // 思路同昨天
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (ans % 2) {
                // 操作了奇数次,需要变化
                nums[i] ^= 1;
            }
            if (nums[i] == 0) ans++;
        }
        return ans;
    }
};