这是小川的第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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!