发表于 2024.08.13

• 有两种做法：第一种则是动态规划，记dp[i][j](其中j = 0, 1)为数组后i个元素构成的子数组(只考虑这i个元素，不考虑前面的翻转影响)翻转为j的最少次数，则如果nums[i] == j，则dp[i][j] = dp[i - 1][j]；否则dp[i][j] = dp[i - 1][1 - j] + 1。最后返回min(dp[n][0], dp[n][1])。

  第二种做法，则是基于上一个问题3191：先考虑第一个元素，如果其为0，则只能通过翻转arr[0..n]将其翻转为1；随后，如果第二个元素此时为0，则只能翻转arr[1..n](因为如果翻转arr[0..n]，则第一个元素又会变为0)；以此类推。那么如何判断第i个元素此时应该为0还是1呢？我们将翻转次数记为k，此时arr[i] = (arr[i] + k) % 2。

  基于DP的做法：

  class Solution:
      def minOperations(self, nums: List[int]) -> int:
          all_zero_cnt = all_one_cnt = 0
          for i in range(len(nums) - 1, -1, -1):
              if nums[i] == 0:
                  all_one_cnt = 1 + all_zero_cnt
              else:
                  all_zero_cnt = 1 + all_one_cnt
          return all_one_cnt

  基于贪心的做法：

  class Solution:
      def minOperations(self, nums: List[int]) -> int:
          ans = 0
          for num in nums:
              if not (num + ans) % 2:
                  ans += 1
          return ans

• LC 题目链接