JZX轻语：简
LeetCode 3192 - 使二进制数组全部等于 1 的最少操作次数 II
发表于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