首页 > 代码库 > leetcode Candy
leetcode Candy
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 }
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 }
leetcode Candy
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。