JZX轻语：简

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

发表于2024年08月13日

使用贪心法，从左到右遍历数组，如果当前元素为0，则将其及后面两个元素都进行翻转。最后判断最后两个元素是否为1(满足全1条件)，如果是则返回操作次数，否则返回-1。

证明上述做法的翻转次数什么是最优的：

首先不难得知，每个(长度为3)子数组的翻转次数至多为1：因为翻转两次相当于不反转，没意义。

其实，我们将翻转操作看作一个序列：如a1->a2->...(即翻转数组nums[a1..a1+2]，翻转数组nums[a2..a2+2]，…)，不难得知，交换序列中的两个操作不影响最终数组结果（本质上每个元素的翻转总次数是确定的，只是翻转的时机不同而已）。

在此基础上，我们可以从左到右处理子数组的翻转：首先处理第一个元素，如果其为0，则只能翻转它及后两个元素(因为只有这个子数组包含第一个元素)arr[0..2]。然后处理第二个元素，如果其为0，则只能翻转它及后两个元素arr[1..3]——因为翻转arr[0..2]只会让第一个元素重新变为0，且如果之前已经翻转过了，再翻转一次就会变回来，没意义。以此类推，直到最后一个元素。

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums) - 2):
            if nums[i] == 1:
                continue
            ans += 1
            for j in range(3):
                nums[i + j] = 1 - nums[i + j]
        if nums[-1] == nums[-2] == 1:
            return ans
        return -1