LeetCode 题解工作台
将珠子放入背包中
你有 k 个背包。给你一个下标从 0 开始的整数数组 weights ，其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k 。 请你按照如下规则将所有的珠子放进 k 个背包。 没有背包是空的。 如果第 i 个珠子和第 j 个珠子在同一个背包里，那么下标在 i 到 j 之间的所有珠子…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
答案摘要
我们可以将问题转化为：将数组 `weights` 分成 个连续的子数组，也就是说，我们要找到 个分割点，每个分割点的价格是分割点左右两个元素的和，求最大的 个分割点的价格之和与最小的 个分割点的价格之和的差值，即为答案。 因此，我们可以处理数组 `weights`，将其转化为一个长度为 的数组 `arr`，其中 `arr[i] = weights[i] + weights[i+1]`，然…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
你有 k 个背包。给你一个下标从 0 开始的整数数组 weights ，其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k 。
请你按照如下规则将所有的珠子放进 k 个背包。
- 没有背包是空的。
- 如果第
i个珠子和第j个珠子在同一个背包里，那么下标在i到j之间的所有珠子都必须在这同一个背包中。 - 如果一个背包有下标从
i到j的所有珠子，那么这个背包的价格是weights[i] + weights[j]。
一个珠子分配方案的 分数 是所有 k 个背包的价格之和。
请你返回所有分配方案中，最大分数 与 最小分数 的 差值 为多少。
示例 1：
输入：weights = [1,3,5,1], k = 2 输出：4 解释： 分配方案 [1],[3,5,1] 得到最小得分 (1+1) + (3+1) = 6 。 分配方案 [1,3],[5,1] 得到最大得分 (1+3) + (5+1) = 10 。 所以差值为 10 - 6 = 4 。
示例 2：
输入：weights = [1, 3], k = 2 输出：0 解释：唯一的分配方案为 [1],[3] 。 最大最小得分相等，所以返回 0 。
提示：
1 <= k <= weights.length <= 1051 <= weights[i] <= 109
解题思路
方法一：问题转化 + 排序
我们可以将问题转化为：将数组 weights 分成 个连续的子数组，也就是说，我们要找到 个分割点，每个分割点的价格是分割点左右两个元素的和，求最大的 个分割点的价格之和与最小的 个分割点的价格之和的差值，即为答案。
因此，我们可以处理数组 weights，将其转化为一个长度为 的数组 arr，其中 arr[i] = weights[i] + weights[i+1]，然后对数组 arr 进行排序，最后求出最大的 个分割点的价格之和与最小的 个分割点的价格之和的差值即可。
时间复杂度 ，空间复杂度 。其中 为数组 weights 的长度。
class Solution:
def putMarbles(self, weights: List[int], k: int) -> int:
arr = sorted(a + b for a, b in pairwise(weights))
return sum(arr[len(arr) - k + 1 :]) - sum(arr[: k - 1])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \log n) |
| 空间 | O(n + S) \approx O(n) |
面试官常问的追问
外企场景- question_mark
Candidate should demonstrate understanding of greedy algorithms and sorting techniques.
- question_mark
Look for proficiency in heap or priority queue usage.
- question_mark
The solution should efficiently handle large input sizes, leveraging sorting and heap structures.
常见陷阱
外企场景- error
Failing to correctly identify the need to separate the largest and smallest weights for optimal score distribution.
- error
Overcomplicating the problem by attempting to find all possible subarray combinations instead of leveraging sorting and greedy methods.
- error
Not optimizing for time complexity, leading to inefficient solutions that fail on large inputs.
进阶变体
外企场景- arrow_right_alt
Instead of maximizing the difference in scores, try to minimize the difference using the same approach.
- arrow_right_alt
Extend the problem to handle more complex scoring mechanisms, such as considering penalties for imbalances.
- arrow_right_alt
Modify the problem to include additional constraints on how marbles can be distributed among bags (e.g., weights must be evenly split).