发表于 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

• LC 题目链接