LeetCode 题解工作台
多次求和构造目标数组
给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作： 令 x 为你数组里所有元素的和 选择满足 0 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。 你可以重复该过程任意次 如果能从 A 开始构造出目标数组 target ，请你返回…
2
题型
6
代码语言
3
相关题
当前训练重点
困难 · 堆
答案摘要
我们发现，如果从数组 开始正向构造目标数组 ，每次都不好确定选择哪个下标 ，问题比较复杂。而如果我们从数组 开始逆向构造，每次构造都一定是选择当前数组中最大的元素，这样就可以保证每次构造都是唯一的，问题比较简单。 因此，我们可以使用优先队列（大根堆）来存储数组 中的元素，用一个变量 记录数组 中所有元素的和。每次从优先队列中取出最大的元素 ，计算当前数组中除 以外的所有元素之和 ，如果…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：
- 令
x为你数组里所有元素的和 - 选择满足
0 <= i < target.size的任意下标i，并让A数组里下标为i处的值为x。 - 你可以重复该过程任意次
如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。
示例 1：
输入：target = [9,3,5] 输出：true 解释：从 [1, 1, 1] 开始 [1, 1, 1], 和为 3 ，选择下标 1 [1, 3, 1], 和为 5， 选择下标 2 [1, 3, 5], 和为 9， 选择下标 0 [9, 3, 5] 完成
示例 2：
输入：target = [1,1,1,2] 输出：false 解释：不可能从 [1,1,1,1] 出发构造目标数组。
示例 3：
输入：target = [8,5] 输出：true
提示：
N == target.length1 <= target.length <= 5 * 10^41 <= target[i] <= 10^9
解题思路
方法一：逆向构造 + 优先队列（大根堆）
我们发现，如果从数组 开始正向构造目标数组 ，每次都不好确定选择哪个下标 ，问题比较复杂。而如果我们从数组 开始逆向构造，每次构造都一定是选择当前数组中最大的元素，这样就可以保证每次构造都是唯一的，问题比较简单。
因此，我们可以使用优先队列（大根堆）来存储数组 中的元素，用一个变量 记录数组 中所有元素的和。每次从优先队列中取出最大的元素 ，计算当前数组中除 以外的所有元素之和 ，如果 或者 ，则说明无法构造目标数组 ，返回 false。否则，我们计算 ，如果 ，则令 ，否则令 ，将 加入优先队列中，并更新 的值，重复上述操作，直到优先队列中的所有元素都变为 ，此时返回 true。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def isPossible(self, target: List[int]) -> bool:
s = sum(target)
pq = [-x for x in target]
heapify(pq)
while -pq[0] > 1:
mx = -heappop(pq)
t = s - mx
if t == 0 or mx - t < 1:
return False
x = (mx % t) or t
heappush(pq, -x)
s = s - mx + x
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is mainly influenced by the heap operations, where each insert and remove operation takes O(log n). With potentially n steps, the overall complexity becomes O(n log n). Space complexity depends on storing the heap, which requires O(n) space. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate optimizes the simulation using a heap for time efficiency.
- question_mark
Look for the candidate's ability to handle edge cases such as arrays with repeated elements.
- question_mark
Evaluate how well the candidate identifies and addresses impossibility conditions.
常见陷阱
外企场景- error
Forgetting to update the heap after each operation, leading to incorrect simulation.
- error
Not correctly handling cases where the largest element cannot be reduced to a valid target.
- error
Inefficient handling of large arrays, resulting in timeouts or excessive space usage.
进阶变体
外企场景- arrow_right_alt
Modify the problem to allow negative numbers and observe how it impacts the approach.
- arrow_right_alt
Consider the impact of different sum operations, such as subtracting a fixed value instead of the total sum.
- arrow_right_alt
Change the constraints to allow non-integer values and assess how the algorithm needs to adapt.