Day 30：100346. 使二进制数组全部等于1的最小操作次数Ⅱ

Leetcode 100346. 使二进制数组全部等于1的最小操作次数Ⅱ

给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：

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

反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。

此题与 Leetcode 100344. 使二进制数组全部等于1的最小操作次数Ⅰ 类似，前者是从下标 i开始连续三个元素反转，此题是从下标i开始一直到数组末尾所有元素反转。
因此不能使用前者的算法：每次遇到 0 的时候，遍历后续所有元素，对其进行反转，这是非常浪费时间的。改进一下：

• 当前元素为 1
  • 已经反转了偶数次，因此经过偶数次反转，值仍为 1，所以不用再反转。
  • 已经反转了奇数次，它的值已经变为 0，因此要反转，反转次数加一。
• 当前元素为 0
  • 已经反转了偶数次，它还是 0，因此要反转，反转次数加一。
  • 已经反转了奇数次，它反转成了 1，因此不用再反转。

完整代码

class Solution {
    public int minOperations(int[] nums) {
        int res = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                if (res % 2 != 0) res++;
            } else {
                if (res % 2 != 1) res++;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14