LeetCode 题解工作台
使二进制数组全部等于 1 的最少操作次数 II
给你一个二进制数组 nums 。 你可以对数组执行以下操作 任意 次（也可以 0 次）： 选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。 反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。 请你返回将 nums 中所有元素变为 1 的 最…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们注意到，每当我们将某个位置的元素变为 1 时，它的右侧的所有元素都会被反转。因此，我们可以用一个变量 来记录当前位置及其右侧的元素是否被反转，如果被反转，那么 的值为 1，否则为 0。 我们遍历数组 ，对于每个元素 ，我们将 与 进行异或运算，如果 为 0，那么我们需要将 变为 1，我们需要进行反转操作，我们将答案加一，并将 取反。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
- 选择数组中 任意 一个下标
i，并将从下标i开始一直到数组末尾 所有 元素 反转 。
反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。
示例 1：
输入：nums = [0,1,1,0,1]
输出：4
解释：
我们可以执行以下操作：
- 选择下标
i = 1执行操作，得到nums = [0,0,0,1,0]。 - 选择下标
i = 0执行操作，得到nums = [1,1,1,0,1]。 - 选择下标
i = 4执行操作，得到nums = [1,1,1,0,0]。 - 选择下标
i = 3执行操作，得到nums = [1,1,1,1,1]。
示例 2：
输入：nums = [1,0,0,0]
输出：1
解释：
我们可以执行以下操作：
- 选择下标
i = 1执行操作，得到nums = [1,1,1,1]。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 1
解题思路
方法一：位运算
我们注意到，每当我们将某个位置的元素变为 1 时，它的右侧的所有元素都会被反转。因此，我们可以用一个变量 来记录当前位置及其右侧的元素是否被反转，如果被反转，那么 的值为 1，否则为 0。
我们遍历数组 ，对于每个元素 ，我们将 与 进行异或运算，如果 为 0，那么我们需要将 变为 1，我们需要进行反转操作，我们将答案加一，并将 取反。
遍历结束后，我们就可以得到最少操作次数。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def minOperations(self, nums: List[int]) -> int:
ans = v = 0
for x in nums:
x ^= v
if x == 0:
ans += 1
v ^= 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the chosen DP implementation, typically O(n) for a linear scan with index tracking. Space complexity varies with auxiliary arrays but is usually O(n) for storing DP states and flip effects. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks if you considered state transitions for every index.
- question_mark
Questions how to minimize redundant flips over consecutive zeros.
- question_mark
Probes understanding of combining greedy steps with dynamic programming.
常见陷阱
外企场景- error
Ignoring the impact of a flip on subsequent positions.
- error
Double-counting operations when tracking state transitions.
- error
Assuming all 0s can be flipped independently without affecting DP state.
进阶变体
外企场景- arrow_right_alt
Minimum flips required to make all elements 0 instead of 1.
- arrow_right_alt
Binary array with weighted flips, where some indices cost more.
- arrow_right_alt
Circular binary array where flips wrap around the end.