- Leetcode 3192. Minimum Operations to Make Binary Array Elements Equal to One II
- 1. 解题思路
- 2. 代码实现
- 题目链接：3192. Minimum Operations to Make Binary Array Elements Equal to One II
1. 解题思路
这一题的话就是一个动态规划，我们使用两个数组one和zero分别记录将所有元素变为1或者0时所需要的操作数目，具体来说，one[i]表示将从第i个元素开始全变为1所需要的操作次数，同理，zero[i]表示将从第i个元素开始全变为0所需要的操作次数。
此时即有递推关系：
- 如果第i个元素为0
one[i] = 1 + zero[i+1]zero[i] = zero[i+1]
- 如果第i个元素为1
one[i] = one[i+1]zero[i] = 1 + one[i+1]
我们返回one[0]即为目标答案。
2. 代码实现
给出python代码实现如下：
class Solution:def minOperations(self, nums: List[int]) -> int:n = len(nums)zero = [0 for _ in range(n+1)]one = [0 for _ in range(n+1)]for i in range(n-1, -1, -1):if nums[i] == 0:zero[i] = zero[i+1]one[i] = 1 + zero[i+1]else:zero[i] = 1 + one[i+1]one[i] = one[i+1]return one[0]
提交代码评测得到：耗时1160ms，占用内存23.2MB。
