题目:
给你一个二进制数组 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;
}
};