首页 > 代码库 > leetcode Candy

leetcode Candy

2024-07-20 00:07:22   220人阅读

1 Candy

题目：

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

解析：

1 先求出相邻小孩的优先级。

2 积分得到每个小孩的糖果数。再加上最小小孩糖果数等于1的限制条件。

3 积分得到总的糖果数。

代码如下：

 1     /* 2      * 优先级相同时，糖果数相同 3      */ 4     private int sign(int i) { 5         if (i > 0) { return 1; } 6         if (i < 0) { return -1; } 7         return 0; 8     } 9     10     private int[] candyDelta(int[] ratings) {11         // delta保存与上一个小孩的优先级12         int[] delta = new int[ratings.length];13         delta[0] = 0;14         for (int i = 1; i < ratings.length; i++) {15             delta[i] = sign(ratings[i] - ratings[i-1]);16         }17         return delta;18     }19     20     private int calCandies(int[] delta) {21         // 计算第一个小孩糖果数为0时，每一个小孩的糖果数。这里糖果数可能为负。22         int[] candies = new int[delta.length];23         candies[0] = 0;24         for (int i = 1; i < candies.length; i++) {25             candies[i] = candies[i-1] + delta[i];26         }27 28         // 找到糖果数最小的小孩29         int min = Integer.MAX_VALUE;30         for (int i = 0; i < candies.length; i++) {31             if (min > candies[i]) {32                 min = candies[i];33             }34         }35         36         // 糖果数最小的小孩给1个糖果，并据此分配糖果给其他小絯37         for (int i = 0; i < candies.length; i++) {38             candies[i] = candies[i] - min + 1; 39         }40         // 计算糖果数41         Integer total = 0;42         for (int candy : candies) {43             total += candy;44         }45         return total;46     }47     48     public int candy(int[] ratings) {   49         if (ratings.length == 1) {50             return 1;51         }52         53         int[] delta = candyDelta(ratings);54 55         int total = calCandies(delta);56 57         return total;58     }
View Code

2 Candy

代码1放到leetcode中，通不过{1,2,2}这个测试用例，返回5，而leetcode结果是4。其原因在于题设中并没有限定两个相邻的rating相同的小孩的糖果数相等。

可以在有相邻小孩rating相同处截断，然后分别计算两部分的candies。

更进一步的，可以从左往右计算，在左边小孩权重不小于右边小孩处截断；然后从右往左计算，在右边小孩权重不小于左边小孩处截断。

即从左往右报数时，第一次的计算结果是满足条件的；从右往左报数时，第二次的计算结果是满足条件的。最后将两次的计算结果合并，即为最终解。

代码如下：

 1     private void calCandies(int[] candies, int[] ratings) { 2         candies[0] = 1; 3         if (ratings.length == 1) { return; } 4          5         // 从左往右 6         int[] candiesLeft = new int[ratings.length]; 7         candiesLeft[0] = 1; 8         for (int i = 1; i < ratings.length; i++) { 9             if (ratings[i] > ratings[i-1]) {10                 candiesLeft[i] = candiesLeft[i-1] + 1;11             }else {12                 candiesLeft[i] = 1;13             }14         }15         16         // 从右往左17         int[] candiesRight = new int[ratings.length];18         candiesRight[ratings.length-1] = 1;19         for (int i = ratings.length-2; i >= 0; i--) {20             if (ratings[i] > ratings[i+1]) {21                 candiesRight[i] = candiesRight[i+1] + 1;22             }else {23                 candiesRight[i] = 1;24             }25         }26         27         // 合并28         for (int i = 0; i < candies.length; i++) {29             candies[i] = Math.max(candiesLeft[i], candiesRight[i]);30         }31     }32 33 34     public int candy(int[] ratings) {35         if (ratings.length == 1) {36             return 1;37         }38 39         int[] candies = new int[ratings.length];40         calCandies(candies, ratings);41 42         // 计算糖果数43         Integer total = 0;44         for (int candy : candies) {45             total += candy;46 47         }48         return total;49     }
View Code

 

leetcode Candy


联系
我们