首页 / 算法 / LeetCode-算法-分糖果
LeetCode-算法-分糖果
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode-算法-分糖果，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7303字，纯文字阅读大概需要11分钟。
内容图文
力扣题目地址：https://leetcode-cn.com/problems/distribute-candies-to-people/
首先看题目：
排排坐，分糖果。
我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。
示例：
示例一：
输入：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]。
示例二：
输入：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
解决思路：
这道题让人第一想到的解法估计就是暴力破解法了。不断计算下一个数组元素需要的糖果数，如果当前剩余糖果树大于需要糖果数，则分配需要的糖果，如果不够则全部分给当前元素；然后返回数组。
我个人不太想这样暴力破解，所以没有采用这种方法，想通过一些规律找出能够节省时间的解法。
这也是这篇博客今天才被发布的原因；接下来给大家讲一讲我的骚操作。
开始我们的解题之旅：
我的大概思路是这样的。首先我知道糖果总数 candies 和数组的元素个数 num_people 。
第一步：因为每个元素分配的糖果都是递增的；所以我可以通过 num_people 知道每一次循环一共需要多少糖果 sum。我们通过 sum 和 candies 比较大小，来计算当前是第几次循环。
第二步：然后根据循环到当前循环的总糖果数减去我们有的糖果总数，计算出差值，然后从当前循环的最后一位反向往前面推导，计算出糖果分完的元素位置end_index。
第三步：计算 end_index 之后，我们可以知道在小于 end_index 的其他元素都是count+1次循环的总和，第 end_index 元素是第count次循环的总和加上剩余糖果数量，大于 end_index 元素的其他元素都是第 count 次循环的总和。
第一步代码实现：
第一次循环分配糖果总和：从 1 到 num_people
递增正整数列求和公式：sum = (1+n)n/2;
循环示例：
第一次循环：1 到 num_people
int sum1 = (1+num_people)*num_people/2;
第二次循环：num_people+1 到 2*num_people
int sum2 = (1+3*num_people)*num_people/2;
第三次循环：2*num_people+1 到 3*num_people
int sum3 = (1+5*num_people)*num_people/2;
第四次循环：3*num_people+1 到 4*num_people
int sum4 = (1+7*num_people)*num_people/2;
总结规律：
完成第 count 次循环所需糖果数量总和：
(1+(2*count-1)*num_people)*num_people/2
代码实现：
//知道了规律我们接下来就可以计算 循环次数
//完成循环次数；从0开始，因为不知道第一次循环的糖果是否能分配完
int count = 0;
//计算完成第一次循环需要的糖果数量
int sum = (1+num_people)*num_people/2;
//算出循环次数 判断总糖果数量是否大于循环增加的糖果数量总和
while (candies > sum){
//循环次数加一
count++;
//计算出下次循环所需要的糖果数 并加入sum
sum += (1+(2*(count+1)-1)*num_people)*num_people/2;
}
第二步代码实现：
1.注意count是完成循环的次数，并不是循环到的次数，所以我们能够循环到第count+1次循环。
2.计算出 candies 数量的糖果能够循环到第 count + 1次之后。
3.我们接下来要考虑的是我们如何定位到 count+1 次循环时,糖果分配完的那个元素位置。
4.首先利用上面计算循环次数的sum和糖果总数candies，计算出完成第count+1次循环所差的糖果值。
反向推导示例：
第 count 次循环最后 1 位所需糖果数：
int sub1 = count*num_people-0;
第 count 次循环倒数第 2 位所需糖果数：
int sub2 = count*num_people-1;
第 count 次循环倒数第 3 位所需糖果数：
int sub3 = count*num_people-2;
第 count 次循环倒数第 4 位所需糖果数：
int sub4 = count*num_people-3;
总结规律：
倒数第 sub_count 位所需要的糖果数：
count*num_people-sub_count
代码实现：
//计算差值
int sub = sum - candies;
//反向推导次数
int sub_count = 0;
//反向推导：倒数第一个位置所需要的糖果数量
int sub_now = (count+1)*num_people-sub_count;
//当剩余糖果数量小于下一个位置所需的糖果数量，说明剩余糖果不够分配给下一个位置了。
while(sub >= sub_now){
//下一个位置所需的糖果数量
sub_now = (count+1)*num_people-sub_count;
//剩余糖果数量减去当前位置所需糖果数量；
sub -= sub_now;
//完成反向推导次数+1
sub_count++;
}
//计算出下一个位置需要的糖果数
sub_now = (count+1)*num_people-sub_count;
//计算出下一个位置剩余的糖果数
sub = sub_now - sub;
//循环到糖果不足的位置
int end_index = num_people - sub_count;
第三步代码实现：
1.计算 end_index 之后;小于 end_index 的其他元素都是count+1次循环的总和。
2.第 end_index 元素是第count次循环的总和加上剩余糖果数量。
3.大于 end_index 元素的其他元素都是第 count 次循环的总和。
元素总和计算示例：
//计算每一位元素需要的值，并放入
第一次循环第一个元素所需糖果数总和：
int number1_1 = 1;
int number1_2 = 2+num_people;(1+1+num_people)
int number1_3 = 3+3*num_people;(1 + 1+num_people + 1+2*num_people)
int number1_4 = 4+6*num_people;
int number1_5 = 5+10*num_people;
int number1_6 = 6+15*num_people;
int number1_7 = 7+21*num_people;
int number1_8 = 8+28*num_people;
第二次循环第一个元素所需糖果数总和：
int number2_1 = 2;
int number2_2 = 4+num_people;
第三次循环第一个元素所需糖果数总和：
int number3_1 = 3;
int number3_2 = 6+num_people;
总结规律：
x 等于从 1 到 count 的和,递增正整数列求和公式：
x = (1+count)*count/2
第 count 次循环 第 i 个位置所需糖果总数：
count*(i+1) + x * num_people
代码实现：
//计算x的值
int x = count*(count+1)/2;
//循环设置值
for(int i = 0; i < num_people; i++) {
if(i < end_index-1){
//1.小于 end_index 的其他元素都是count+1次循环的总和。
result[i] = (count+1)*(i+1) + x * num_people;
}else if(i == end_index-1){
//2.第 end_index 元素是第count次循环的总和加上剩余糖果数量。
result[i] = count*(i+1) +(x-count) * num_people + sub;
}else{
//3.大于 end_index 元素的其他元素都是第 count 次循环的总和。
result[i] = count*(i+1) +(x-count) * num_people;
}
}
完整代码：
/**
* 分糖果 https://leetcode-cn.com/problems/distribute-candies-to-people/
* @param candies
* @param num_people
* @author GeYuxuan 2020-03-06 22:18:03
* @return int[]
*/
public int[] distributeCandies(int candies, int num_people) {
int [] result = new int[num_people];
//循环次数
int count = 0;
int sum = (1+num_people)*num_people/2;
//算出循环次数
while (candies > sum){
//循环次数加一
count++;
//计算出下次循环所需要的糖果数 并加入sum
sum += (1+(2*(count+1)-1)*num_people)*num_people/2;
}
//计算差值
int sub = sum - candies;
int sub_count = 0;
int sub_now = (count+1)*num_people-sub_count;
while(sub >= sub_now){
sub_now = (count+1)*num_people-sub_count;
sub -= sub_now;
sub_count++;
}
sub_now = (count+1)*num_people-sub_count;
sub = sub_now - sub;
//循环到余额不足的位置
int end_index = num_people - sub_count;
//计算count总和
int x = count*(count+1)/2;
//计算每一位需要的值，并放入
for(int i = 0; i < num_people; i++) {
if(i < end_index-1){
result[i] = (count+1)*(i+1) + x * num_people;
}else if(i == end_index-1){
result[i] = count*(i+1) +(x-count) * num_people + sub;
}else{
result[i] = count*(i+1) +(x-count) * num_people;
}
}
return result;
}
这篇博客是3月5号应该发出的文章，但是当天晚上3个小时还是没有解出这道题目，其实在中间我有想过放弃这种解法，但是我一直没有想明白我的解法哪里有问题。因为第二天还要上班，为了不影响上班，这题我打算第二天有空再解。直到第二天晚上有时间去解出这道题的时候，我是十分兴奋；我觉得暴力解法永远都是最后的方法，只有动脑子才会让脑子变得灵活。
不忘初心，砥砺前行。
内容总结
以上是互联网集市为您收集整理的LeetCode-算法-分糖果全部内容，希望文章能够帮你解决LeetCode-算法-分糖果所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。