LeetCode 每日一题 使二进制数组全部等于 1 的最少操作次数 I

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

给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
选择数组中 任意连续 3 个元素，并将它们 全部反转 。
反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。如果无法全部变成 1 ，返回 -1 。
示例 1：
输入：nums = [0,1,1,1,0,0]
输出：3
解释：
我们可以执行以下操作：
选择下标为 0 ，1 和 2 的元素并反转，得到 nums = [1,0,0,1,0,0] 。
选择下标为 1 ，2 和 3 的元素并反转，得到 nums = [1,1,1,0,0,0] 。
选择下标为 3 ，4 和 5 的元素并反转，得到 nums = [1,1,1,1,1,1] 。
示例 2：
输入：nums = [0,1,1,1]
输出：-1
解释：
无法将所有元素都变为 1 。
提示：
3 <= nums.length <= 105
0 <= nums[i] <= 1

题解

根据题意，我们需要进行将一个数组的第 i 到 i+2 的元素 ^ 1 ，使得数组的全部元素变成1

求得这一操作的最少次数

如果无法全部变成 1 就返回 -1

首先，我们对操作进行思考

对一个位置 i ，最多只能进行一次操作，因为操作两次就相当于没有操作，白白浪费次数，更多次数同理

接着

操作的顺序对结果是没有影响的，先对 i 操作再 操作 j 与先 j 后 i 得到的结果是一致的

那么也就是说，对于任意的操作，操作的顺序可以是任意的

我们不妨从左至右进行操作

用 res 记录操作次数

对数组进行遍历，最多遍历到倒数第三个，因为要对位置的后两个进行操作，防止越界

假如此时数据是 1 则不进行操作，i++

如果此时数据是 0 则必须要操作，否则不可能使数组全为 1 ，即对 i 至 i+2 的数据 ^ 1 ，res++，i++

循环结束的时候，假如数组的最后两个数据都是 1 则说明数组全是1，返回 res

否则说明无法达到全是1，返回 -1

那么为什么这样操作就是最少的次数呢？
因为对同一个 i 至多操作一次，就可以做到最少的操作次数

代码如下↓

int minOperations(int* nums, int numsSize) {
    int res=0;
    for(int i=0;i<numsSize-2;i++)
    {
        if(nums[i]==1)
        {
            continue;
        }
        else
        {
            nums[i]^=1;
            nums[i+1]^=1;
            nums[i+2]^=1;
            res++;
        }
    }
    if(nums[numsSize-2] && nums[numsSize-1])
    {
        return res;
    }
    else
    {
        return -1;
    }
}