这是小川的第393次更新，第425篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第256题（顺位题号是1103）。我们通过以下方式向一排n = num_people个人分发一些糖果：
给第一个人送1个糖果，给第二个人送2个糖果，依此类推，直到我们给最后一个人送糖果。然后，我们回到行的开头，向第一个人提供n + 1个糖果，向第二个人提供n + 2个糖果，依此类推，直到我们向最后一个人提供2 * n个糖果。
这个过程重复进行，直到我们用完糖果。最后一个人将得到所有剩余的糖果（不一定比之前收到的多）。
返回一个数组（长度为num_people，元素总和为candies），代表糖果的最终分配结果。
例如：
输入：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,2,3,1]。
输入：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
02 第一种解法
暴力解法。
直接使用两层循环，外层控制candies的剩余量，内层循环n次，定义一个变量sum，从1开始自增，代表每次要分出去的糖果数量，内层循环中，每遍历一次，sum加1，同时candies要减去sum，如果最后剩余的糖果小于了本次预计要分配的数量，就将剩余的糖果全给当前这个人，candies为0，循环结束。
public int[] distributeCandies(int candies, int num_people) {
int[] result = new int[num_people];
int sum = 1;
while (candies > 0) {
for (int i=0; i<result.length; i++) {
if (candies - sum> 0) {
result[i] += sum;
candies -= sum;
sum++;
} else {
result[i] += candies;
candies = 0;
break;
}
}
}
return result;
}03 第二种解法
我们还可以对第一种解法再优化下，变成一层循环，借助取余来实现。
因为每执行一次从头到尾的分配，都是从第一个人到第n个人，可以利用数组的下标对n取余来替代，其他处理逻辑不变。
public int[] distributeCandies2(int candies, int num_people) {
int[] result = new int[num_people];
int sum = 1;
for (int i=0; candies > 0; i++) {
if (candies - sum> 0) {
result[i%num_people] += sum;
candies -= sum;
sum++;
} else {
result[i%num_people] += candies;
break;
}
}
return result;
}04 第三种解法
我们还可以对第二种解法再优化下，省掉循环方法体里面的if判断。
结果数组的索引是从0开始的，代表第一个人，那他被分配的糖果数量是索引值加1，在前面两种解法中，都使用了if判断candies是不是比当前需要分配出去的糖果大，其实就是取两者之间的较小值。
如果candies剩余的数量比当前需要分配出去的糖果数量大，就可以继续分配；如果candies剩余的数量比当前需要分配出去的糖果数量小，说明当前这次分配时最后一次分配，只能将剩余的糖果数量全部分给当前此人了。
public int[] distributeCandies3(int candies, int num_people) {
int[] result = new int[num_people];
for (int i=0; candies > 0; i++) {
result[i%num_people] += Math.min(candies, i+1);
candies -= i+1;
}
return result;
}05 小结
算法专题目前已连续日更超过八个月，算法题文章262+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
- 还没有人评论，欢迎说说您的想法！
客服
