[LeetCode] 3191. Minimum Operations to Make Binary Array Elements Equal to One I

You are given a binary array nums.

You can do the following operation on the array any number of times (possibly zero):

Choose any 3 consecutive elements from the array and flip all of them.
Flipping an element means changing its value from 0 to 1, and from 1 to 0.

Return the minimum number of operations required to make all elements in nums equal to 1. If it is impossible, return -1.

Example 1:
Input: nums = [0,1,1,1,0,0]
Output: 3

Explanation:
We can do the following operations:
Choose the elements at indices 0, 1 and 2. The resulting array is nums = [1,0,0,1,0,0].
Choose the elements at indices 1, 2 and 3. The resulting array is nums = [1,1,1,0,0,0].
Choose the elements at indices 3, 4 and 5. The resulting array is nums = [1,1,1,1,1,1].

Example 2:
Input: nums = [0,1,1,1]
Output: -1

Explanation:
It is impossible to make all elements equal to 1.

Constraints:
3 <= nums.length <= 105
0 <= nums[i] <= 1

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

给你一个二进制数组 nums 。

你可以对数组执行以下操作 任意 次（也可以 0 次）：

选择数组中 任意连续 3 个元素，并将它们 全部反转 。
反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。

请你返回将 nums 中所有元素变为 1 的 最少 操作次数。如果无法全部变成 1 ，返回 -1 。

思路

思路是贪心。题目要求我们要把 input 数组里所有的 0 变成 1，一次只能变 3 个，同时操作的次数要最小。如果某个数字是 0，我们一定要对他操作一次或者操作单数次，因为如果操作偶数次的话只会是把 0 变成 1，然后又变回 0，这样做是没有意义的。

所以我们可以遍历数组，如果当前位置上的数字是 0，我们就对他操作一次，然后再对后面两个数字操作一次，这样就可以把当前位置上 0 变成 1 了。遍历是从 index = 0 到 index = n - 2。如果最后两个位置上的数字有 0，则说明无法将所有数字都翻转成 1，返回 -1。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] == 0) {
                count++;
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
            }
        }
        if (nums[n - 1] == 0 || nums[n - 2] == 0) {
            return -1;
        }
        return count;
    }
}
JAVA