LeetCode 1103. 分糖果 II
题目描述
题意分析
小朋友按固定顺序排成一圈，从第一个人开始，计划依次发一颗、两颗、三颗，之后每次比上一次多一颗。走过最后一个人后回到第一个人，但计划发放量继续增长，不会重新从一开始。
糖果不足本次计划数量时，把剩下的全部发给当前人，然后结束。返回每个人累计收到的糖果数，而不是最后一次收到的数量；有的人可能收多次，也可能还没有轮到就已经发完。
解法：模拟发放
核心思路
[!blue]
直接以“发放一次”为循环单位。变量
give同时表示本次是第几次发放，以及正常情况下应发多少颗；它从一开始不断增加。人数设为p，当前接收者的零基下标是(give - 1) % p，取模只让接收位置循环，不影响发放量继续增加。每次实际发出的数量是
cur = min(candies, give)。糖果足够就按计划发放，不够就一次发光；将cur累加到接收者答案，并从剩余糖果中扣除同一个数量。这样已发数量与剩余数量之和始终等于初始总数，不会凭空多发或留下未分配的尾数。循环只要求剩余糖果大于零。因为每轮实际发放至少一颗，剩余量严格减少；最后不足计划量时也会进入循环，由取最小值的规则自然结束。同一个人再次被轮到时使用累加，保留之前所有轮次的收获。
虽然初始糖果数可能很大，但循环不是逐颗发。前
t次完整发放消耗t(t + 1) / 2颗糖，增长为平方量级，因此最多执行平方根量级的完整发放，再加至多一次收尾。直接模拟已经足以处理题目的范围。
解题步骤
- 创建长度为人数的零数组，令
give = 1。- 剩余糖果非零时，用
(give - 1) % p找到接收者。- 将实际数量
min(candies, give)累加给他，并从剩余糖果中扣除。- 将
give加一，直到糖果耗尽，返回累计数组。
代码实现
class Solution {
public int[] distributeCandies(int candies, int num_people) {
int[] res = new int[num_people];
for (int give = 1; candies > 0; give++) {
// 发放量一直递增，只有接收人的下标循环回到开头。
int idx = (give - 1) % num_people;
// 取较小值同时覆盖正常发放与最后一次发光两种情况。
int cur = Math.min(candies, give);
res[idx] += cur;
candies -= cur;
}
return res;
}
}
func distributeCandies(candies int, numPeople int) []int {
res := make([]int, numPeople)
for give := 1; candies > 0; give++ {
// 发放量一直递增，只有接收人的下标循环回到开头。
idx := (give - 1) % numPeople
// 取较小值同时覆盖正常发放与最后一次发光两种情况。
cur := give
if candies < cur {
cur = candies
}
res[idx] += cur
candies -= cur
}
return res
}
复杂度分析
- 时间复杂度：$O(p + \sqrt C)$，
p为人数，C为初始糖果数。结果初始化需要 $O(p)$，实际发放次数为 $O(\sqrt C)$。- 空间复杂度：返回数组占 $O(p)$，除此之外只保存发放量、剩余量和下标，辅助空间为 $O(1)$。
关键点总结
[!green]
- 接收位置按人数循环，计划发放量始终递增，二者不能一起重置。
- 使用实际发放量同时更新结果和剩余量，统一处理最后不足的一次。
- 模拟次数由三角数增长决定，是平方根量级，不是糖果总数那么多轮。
易错点总结
[!yellow]
- 回到队首时把发放量也重置为一，改变了题目要求的递增序列。
- 给结果累加计划数量、却只扣除剩余糖果，会在最后一轮多记糖果。
- 循环只在糖果足够计划量时执行，会遗漏最后不够一次的剩余糖果。
- 用赋值覆盖某人的结果，会丢掉他在前几轮收到的糖果。
- 下标写成
give % p，会从第二个人开始，偏移了接收顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 441. 排列硬币 | 简单 | 完整发放1、2、3等数量的次数可由三角数确定，再按接收者位置汇总等差序列。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！