-
发表于 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 题目链接
-