当前位置：首页 > news >正文

LeetCode -- Candy

news 来源：原创 2024/5/19 6:14:03

题目：

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个rating数组，表示每个娃所得的评分。现在要求：
1.给每个娃至少分1个candy
2.分高的娃要比邻居所得的candy多
3.尽量少分candy

思路：
此题采用贪心法。

贪心策略：
1. 先分给谁？从得分最少的娃开始分，因此不妨构造child对象，对得分排序，以此存入child。
2. 分多少？由于是按照得分从低到高分candy的。如果邻居已经有人得了candy，那么就分别将当前娃的得分与左右两边娃进行对比：
a.如果当前得分与左或右相等，只给1个
b.如果当前得分大于左或右，需要给对方所得的candy数+1个
综合a,b，取最大的那个。

如果两边没人得candy，只给当前娃1个。

实现代码：

class Child
{
	public Child(int i , int v){
		index = i;
		rating = v;
	}
	
	public int index;
	public int rating;
}


public int Candy(int[] ratings) 
{
if(ratings == null || ratings.Length == 0){
	return 0;
}


if(ratings.Length == 1){
	return 1;
}


var arr = new List<Child>();
var candies = new int[ratings.Length];
    for(var i = 0 ;i < ratings.Length; i++){
	candies[i] = 0;
	arr.Add(new Child(i, ratings[i]));
}


arr = arr.OrderBy(x=>x.rating).ToList();


for(var i = 0 ;i < arr.Count ; i++){
	var index = arr[i].index;
	if(candies[index] != 0){
		continue;
	}
	
	if(index == 0){
		candies[index] = ratings[index] == ratings[index + 1]  ? 1 : candies[index + 1] + 1;
	}
	else if(index == candies.Length - 1){
		candies[index] = ratings[index] == ratings[index - 1]  ? 1 : candies[index - 1] + 1;
	}
	else{
		var left = ratings[index-1] == ratings[index] ? 1 : candies[index - 1] + 1;
		var right = ratings[index+1] == ratings[index] ? 1 : candies[index + 1] + 1;
		
		candies[index] = Math.Max(left , right);
	}
	
}


var s = 0;
for(var i = 0;i < candies.Length; i++){
	s += candies[i];
}


return s;
}