1103. 分糖果 II
1103. 分糖果 II
题目
We distribute some number of candies
, to a row of n = num_people
people in the following way:
We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n
candies to the last person.
Then, we go back to the start of the row, giving n + 1
candies to the first person, n + 2
candies to the second person, and so on until we give 2 * n
candies to the last person.
This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).
Return an array (of length num_people
and sum candies
) that represents the final distribution of candies.
Example 1:
Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].
Example 2:
Input: candies = 10, num_people = 3
Output: [5,2,3]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0].
On the third turn, ans[2] += 3, and the array is [1,2,3].
On the fourth turn, ans[0] += 4, and the final array is [5,2,3].
Constraints:
- 1 <= candies <= 10^9
- 1 <= num_people <= 1000
题目大意
排排坐,分糖果。
我们买了一些糖果 candies
,打算把它们分给排好队的 n = num_people
个小朋友。
给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类推,直到给最后一个小朋友 n
颗糖果。
然后,我们再回到队伍的起点,给第一个小朋友 n + 1
颗糖果,第二个小朋友 n + 2
颗,依此类推,直到给最后一个小朋友 2 * n
颗糖果。
重复上述过程(每次都比上一次多给出一颗糖果,当到达队伍终点后再次从队伍起点开始),直到我们分完所有的糖果。注意,就算我们手中的剩下糖果数不够(不比前一次发出的糖果多),这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people
、元素之和为 candies
的数组,以表示糖果的最终分发情况(即 ans[i]
表示第 i
个小朋友分到的糖果数)。
示例 1:
输入: candies = 7, num_people = 4
输出:[1,2,3,1]
解释:
第一次,ans[0] += 1,数组变为 [1,0,0,0]。
第二次,ans[1] += 2,数组变为 [1,2,0,0]。
第三次,ans[2] += 3,数组变为 [1,2,3,0]。
第四次,ans[3] += 1(因为此时只剩下 1 颗糖果),最终数组变为 [1,2,3,1]。
示例 2:
输入: candies = 10, num_people = 3
输出:[5,2,3]
解释:
第一次,ans[0] += 1,数组变为 [1,0,0]。
第二次,ans[1] += 2,数组变为 [1,2,0]。
第三次,ans[2] += 3,数组变为 [1,2,3]。
第四次,ans[0] += 4,最终数组变为 [5,2,3]。
提示:
1 <= candies <= 10^9
1 <= num_people <= 1000
解题思路
创建一个长度为
num_people
的数组arr
,表示每个人获得的糖果数,初始值为0
。逐轮分发糖果:
- 从第
1
颗糖果开始分发,每轮将当前数量的糖果分配给(cur - 1) % num_people
对应的人。 - 更新剩余糖果数
candies
:每次分配糖果后减去本轮分配的数量candy
。
- 从第
如果本轮需要分发的糖果
cur
大于剩余糖果candies
,只分发剩余的所有糖果。糖果分发完毕后,返回数组
arr
。
复杂度分析
- 时间复杂度:
O(√candies)
- 每次分发的糖果数量递增,因此分发完成后
cur ≈ √(2 * candies)
。 - 故 while 循环执行次数为
O(√candies)
。
- 每次分发的糖果数量递增,因此分发完成后
- 空间复杂度:
O(num_people)
,仅使用一个大小为num_people
的数组存储结果。
代码
/**
* @param {number} candies
* @param {number} num_people
* @return {number[]}
*/
var distributeCandies = function (candies, num_people) {
// 初始化数组
let arr = new Array(num_people).fill(0);
let cur = 1; // 当前分发的糖果数量
// 模拟分发过程
while (candies > 0) {
// 计算本轮分发的糖果数量
const candy = candies >= cur ? cur : candies;
// 分发糖果
arr[(cur - 1) % num_people] += candy;
// 更新剩余糖果数
candies -= candy;
// 更新当前分发的糖果数量
cur++;
}
return arr; // 返回分发结果
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2591 | 将钱分给最多的儿童 | 贪心 数学 | 🟢 | 🀄️ 🔗 |