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

> Problem: 3191. 使二进制数组全部等于 1 的最少操作次数 I

题目描述

给定一个二进制数组 nums，你可以对数组执行任意次数的操作，每次操作可以选择连续的三个元素，将它们全部反转（即 0 变 1，1 变 0）。你的任务是计算将数组中的所有元素变为 1 的最少操作次数。如果无法将所有元素变为 1，返回 -1。

示例

输入：nums = [0, 1, 1, 1, 0, 0]

输出：3

解释：

第一次选择下标为 0, 1, 2 的元素进行反转，得到 [1, 0, 0, 1, 0, 0]。
第二次选择下标为 1, 2, 3 的元素进行反转，得到 [1, 1, 1, 0, 0, 0]。
第三次选择下标为 3, 4, 5 的元素进行反转，得到 [1, 1, 1, 1, 1, 1]。

解题思路

这道题本质上是通过一次次局部的反转操作，尽可能将所有 0 变为 1。由于每次只能操作连续的 3 个元素，我们可以使用贪心策略逐步处理数组。

关键点分析：

贪心思想：
我们遍历数组时，每当遇到一个 0 时，就需要通过反转来将其变为 1。因为我们一次只能反转连续的三个元素，遇到 0 时，我们尽量从当前位置开始向后反转三个元素。
终止条件：
当数组快结束时（即剩下的元素不足三个），如果我们依然遇到 0，那将无法再反转更多元素。这种情况下，直接返回 -1，表示无法将数组全变为 1。

具体步骤：

遍历数组：
- 如果遇到 0，检查当前位置是否能向后反转 3 个元素。如果可以，就执行反转，并记录反转次数；如果剩余元素不足 3 个，直接返回 -1。
继续遍历直到数组结束，最后返回记录的操作次数。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int cnt = 0;  // 记录操作次数
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                // 如果当前 0 后面不足三个元素，无法完成反转
                if (i > n - 3) {
                    return -1;
                }
                // 每遇到 0 就反转当前和接下来的两个元素
                cnt++;
                nums[i] ^= 1;  // 异或操作，将 0 变 1
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
            }
        }
        
        return cnt;  // 返回最少操作次数
    }
};

示例解析

示例1：

输入: nums = [0, 1, 1, 1, 0, 0]

我们通过以下步骤将所有元素变为 1：

遇到下标 0 处的 0，反转下标 0, 1, 2 三个位置，数组变为 [1, 0, 0, 1, 0, 0]，操作次数增加 1。
再次遇到下标 1 处的 0，反转下标 1, 2, 3 三个位置，数组变为 [1, 1, 1, 0, 0, 0]，操作次数增加 1。
继续遇到下标 3 处的 0，反转下标 3, 4, 5 三个位置，数组变为 [1, 1, 1, 1, 1, 1]，操作次数增加 1。

最终结果为 3 次操作将所有元素变为 1，返回 3。

示例2：

输入: nums = [1, 1, 0]

我们遇到下标 2 处的 0，然而由于剩余的元素不足三个，无法执行反转，因此返回 -1。

复杂度分析

时间复杂度：O(n)，遍历数组一次即可完成解答。
空间复杂度：O(1)，我们对数组进行了原地修改，未使用额外的空间。

总结

这道题采用贪心策略，每次遇到 0 时都尽量通过反转操作去消除它。如果末尾剩余的元素不足三个，我们直接返回 -1，表示无法完成任务。通过位运算异或操作，我们能够高效地进行元素的反转，使得整体的实现简洁高效。

秒客网