LeetCode 题解工作台
对数组执行操作
给你一个下标从 0 开始的数组 nums ，数组大小为 n ，且由 非负 整数组成。 你需要对数组执行 n - 1 步操作，其中第 i 步操作（从 0 开始计数）要求对 nums 中第 i 个元素执行下述指令： 如果 nums[i] == nums[i + 1] ，则 nums[i] 的值变成原来的…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 双·指针·invariant
答案摘要
我们直接根据题意模拟即可。 首先，我们遍历数组 ，对于任意相邻的两个元素 和 ，如果 ，那么我们将 的值变为原来的 倍，同时将 的值变为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个下标从 0 开始的数组 nums ，数组大小为 n ，且由 非负 整数组成。
你需要对数组执行 n - 1 步操作，其中第 i 步操作（从 0 开始计数）要求对 nums 中第 i 个元素执行下述指令：
- 如果
nums[i] == nums[i + 1]，则nums[i]的值变成原来的2倍，nums[i + 1]的值变成0。否则，跳过这步操作。
在执行完 全部 操作后，将所有 0 移动 到数组的 末尾 。
- 例如，数组
[1,0,2,0,0,1]将所有0移动到末尾后变为[1,2,1,0,0,0]。
返回结果数组。
注意 操作应当 依次有序 执行，而不是一次性全部执行。
示例 1：
输入：nums = [1,2,2,1,1,0] 输出：[1,4,2,0,0,0] 解释：执行以下操作： - i = 0: nums[0] 和 nums[1] 不相等，跳过这步操作。 - i = 1: nums[1] 和 nums[2] 相等，nums[1] 的值变成原来的 2 倍，nums[2] 的值变成 0 。数组变成 [1,4,0,1,1,0] 。 - i = 2: nums[2] 和 nums[3] 不相等，所以跳过这步操作。 - i = 3: nums[3] 和 nums[4] 相等，nums[3] 的值变成原来的 2 倍，nums[4] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。 - i = 4: nums[4] 和 nums[5] 相等，nums[4] 的值变成原来的 2 倍，nums[5] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。 执行完所有操作后，将 0 全部移动到数组末尾，得到结果数组 [1,4,2,0,0,0] 。
示例 2：
输入：nums = [0,1] 输出：[1,0] 解释：无法执行任何操作，只需要将 0 移动到末尾。
提示：
2 <= nums.length <= 20000 <= nums[i] <= 1000
解题思路
方法一：模拟
我们直接根据题意模拟即可。
首先，我们遍历数组 ，对于任意相邻的两个元素 和 ，如果 ，那么我们将 的值变为原来的 倍，同时将 的值变为 。
然后，我们创建一个长度为 的答案数组 ，并将 中所有非零元素按顺序放入 中。
最后，返回答案数组 即可。
时间复杂度 ，其中 是数组 的长度。忽略答案的空间消耗，空间复杂度 。
class Solution:
def applyOperations(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(n - 1):
if nums[i] == nums[i + 1]:
nums[i] <<= 1
nums[i + 1] = 0
ans = [0] * n
i = 0
for x in nums:
if x:
ans[i] = x
i += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is scanned once for doubling and once for zero-shifting. Space complexity is O(1) since operations modify the array in-place without additional storage. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Do you understand how to detect adjacent equal values efficiently?
- question_mark
Can you maintain element order while moving zeros to the end?
- question_mark
Will your approach handle the full range of array lengths within O(n) time?
常见陷阱
外企场景- error
Forgetting to set the second element to zero after doubling, breaking the simulation invariant.
- error
Using nested loops for zero-shifting, which increases time complexity unnecessarily.
- error
Altering the relative order of non-zero elements when moving zeros to the end.
进阶变体
外企场景- arrow_right_alt
Apply similar operations but triple the first element instead of doubling if adjacent elements match.
- arrow_right_alt
Allow operations to skip a fixed number of elements instead of only adjacent pairs.
- arrow_right_alt
Modify the problem to handle negative numbers while still doubling and shifting zeros.