LeetCode 题解工作台
数组元素相等转换
给你一个大小为 n 的整数数组 nums ，其中只包含 1 和 -1 ，以及一个整数 k 。 你可以最多进行 k 次以下操作： 选择一个下标 i （ 0 ），然后将 nums[i] 和 nums[i + 1] 同时 乘以 -1 。 注意： 你可以在 不同 的操作中多次选择相同的下标 i 。 如果在最…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
根据题目描述，要使得数组的所有元素相等，要么所有元素为 ，要么所有元素为 。因此，我们设计一个函数 ，用于判断在最多 次操作后，数组能否变成所有元素为 的形式。 该函数的思路是遍历数组，记录需要进行操作的次数。一个元素要么修改一次，要么不修改。如果当前元素与目标值相等，则不需要修改，继续遍历下一个元素；如果当前元素与目标值不相等，则需要修改，计数器加一，并将符号切换为负数，表示后续元素需要进行…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个大小为 n 的整数数组 nums，其中只包含 1 和 -1，以及一个整数 k。
你可以最多进行 k 次以下操作：
-
选择一个下标
i（0 <= i < n - 1），然后将nums[i]和nums[i + 1]同时 乘以-1。
注意：你可以在 不同 的操作中多次选择相同的下标 i。
如果在最多 k 次操作后可以使数组的所有元素相等，则返回 true；否则，返回 false。
示例 1：
输入： nums = [1,-1,1,-1,1], k = 3
输出： true
解释：
我们可以通过以下两次操作使数组的所有元素相等：
- 选择下标
i = 1，将nums[1]和nums[2]同时乘以 -1。此时nums = [1,1,-1,-1,1]。 - 选择下标
i = 2，将nums[2]和nums[3]同时乘以 -1。此时nums = [1,1,1,1,1]。
示例 2：
输入： nums = [-1,-1,-1,1,1,1], k = 5
输出： false
解释：
在最多 5 次操作内，无法使数组的所有元素相等。
提示：
1 <= n == nums.length <= 105nums[i]的值为-1或1。1 <= k <= n
解题思路
方法一：遍历计数
根据题目描述，要使得数组的所有元素相等，要么所有元素为 ，要么所有元素为 。因此，我们设计一个函数 ，用于判断在最多 次操作后，数组能否变成所有元素为 的形式。
该函数的思路是遍历数组，记录需要进行操作的次数。一个元素要么修改一次，要么不修改。如果当前元素与目标值相等，则不需要修改，继续遍历下一个元素；如果当前元素与目标值不相等，则需要修改，计数器加一，并将符号切换为负数，表示后续元素需要进行相反的操作。
如果遍历结束后，计数器小于等于 且最后一个元素的符号与目标值相同，则返回 ，否则返回 。
最终答案是 或 的结果。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
class Solution:
def canMakeEqual(self, nums: List[int], k: int) -> bool:
def check(target: int, k: int) -> bool:
cnt, sign = 0, 1
for i in range(len(nums) - 1):
x = nums[i] * sign
if x == target:
sign = 1
else:
sign = -1
cnt += 1
return cnt <= k and nums[-1] * sign == target
return check(nums[0], k) or check(-nums[0], k)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for a single pass counting operations towards each target. Space complexity is O(1) using counters without additional structures, both dependent on linear array length. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks for operation minimization strategy using greedy plus invariant reasoning.
- question_mark
Checks if you handle repeated index selections correctly and do not overcount operations.
- question_mark
Evaluates understanding of edge cases with alternating patterns or already uniform segments.
常见陷阱
外企场景- error
Ignoring the possibility of choosing the same index multiple times, leading to incorrect operation count.
- error
Failing to consider both targets separately, missing a valid solution path.
- error
Assuming contiguous flips always reduce operations, violating the invariant constraint in some arrangements.
进阶变体
外企场景- arrow_right_alt
Transform array with values from {1, -1, 0} to a single target with limited k operations.
- arrow_right_alt
Minimize operations to equalize array elements when allowed operation can flip up to m contiguous elements.
- arrow_right_alt
Determine maximum length prefix that can be made uniform within k operations using the same greedy invariant pattern.