【LeetCode】分发糖果系列问题(I、II、III)

(一)分糖果

题目(Easy): 575. 分糖果

题目描述:

给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例 :

输入: candies = [1,1,2,2,3,3]

输出: 3

解析: 一共有三种种类的糖果,每一种都有两个。 最优分配方案:妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

解题思路:

  本题比较简单,实际上就是将n个糖果分给两个人,而总共有偶数个糖果,每个人都是正好分一半,假设为len/2,那么存在两种情况:

  • 如果 糖果种类数少于 len/2, 那么妹妹可以得到的种类数最多就等于种类数,不可能更多

  • 如果 种类数多余 len/2,那么妹妹可以得到的种类数最多也就只有 len/2

    所以,本题的关键就是得到糖果总的种类数,种类数可以通过Set得到。

class Solution {
    public int distributeCandies(int[] candies) {
        if(candies==null || candies.length==0)
            return 0;
        int len=candies.length;
        Set<Integer> set=new HashSet<>();
        for(int c:candies)
            set.add(c);
        return Math.min(set.size(),len/2);
    }
}

(二)分糖果II

题目(Easy)1103. 分糖果 II

题目描述:

排排坐,分糖果。

我们买了一些糖果 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]。

解题思路:

本题同样不难解决,实际上这是等差数列的一个应用,可以通过数学推导来得到对应的公式。除此之外,这里我们可以通过迭代模拟糖果的发放过程,同样可以较快的解决本题,具体见代码。

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int[] res=new int[num_people];

        int num=1;
        for(int i=0;i<num_people;i++){
            if(candies>=num){
                res[i]+=num;
                candies-=num;
            }else{
                res[i]+=candies;
                break;
            }

            if(i==num_people-1)
                i=-1;
            num+=1;
        }
        return res;
    }
}

(三)分发糖果

题目(hard):135. 分发糖果

题目描述:

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

你需要按照以下要求,帮助老师给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。

  • 相邻的孩子中,评分高的孩子必须获得更多的糖果。

那么这样下来,老师至少需要准备多少颗糖果呢?

示例 1:

输入: [1,0,2]

输出: 5

解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

解题思路(动态规划):

  相比前两道,本题难度较大。我们把给每个人分多少个糖果作为一次决策,比如给第i个孩子分配糖果,这要取决于第i-1和第i+1个孩子的分配情况,因为这取决于相邻孩子的分发情况。

  也就是说:假如我们知道了 i - 1 和 i + 1 个孩子分配的糖果个数,那么给第 i 个孩子分配糖果个数的问题就迎刃而解了,这可以分成两种情况:

  • 相邻的孩子中,评分高 且站在右边 的孩子必须获得更多的糖果
  • 相邻的孩子中,评分高 且站在左边 的孩子必须获得更多的糖果

​ 针对第1个问题,我们把解决 i 的问题 转换为了 i - 1 的子问题;从前到后扫描一遍即可

​ 针对第2个问题,我们把解决 i 的问题 转换为了 i + 1 的子问题,从后到前扫描一遍,此时,与前一遍扫描计算的结果相比,取最大值

class Solution {
    public int candy(int[] ratings) {
        //两次动态规划
        int len=ratings.length;
        int[] res=new int[len];
        res[0]=1;
        //从前往后扫描
        for(int i=1;i<len;i++){
            res[i]=1;
            if(ratings[i]>ratings[i-1])  //评分高,站在右边
                res[i]=res[i-1]+1;
        }
        
        //从后往前扫描
        for(int i=len-2;i>=0;i--){
            if(ratings[i] > ratings[i+1])  //评分高,站在左边
                res[i]=Math.max(res[i],res[i+1]+1);
        }
        
        int result=0;
        for(int t:res)
            result+=t;
        return result;
    }
}

总结

以上三题都以分发糖果为背景,前两题比较简单,特别是第三题从前往后和从后往前进行两次动态规划的思想,有眼前一亮的感觉,非常巧妙,值得借鉴和思考。

上一篇:POJ3159:Candies(差分约束)


下一篇:【leetcode】1298. Maximum Candies You Can Get from Boxes