[LeetCode]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?

题目大意:

有N个孩子站成一排。每一个孩子都被赋予一个评分。

你现在为这些孩子分配糖果,需要满足下面的要求:

每一个孩子至少要分得1个糖果。

评分高的孩子得到的糖果要多余他的邻居(左右两边)。

你最少要给出多少个糖果?

解题思路:

贪心算法(Greedy Algorithm)

评分同时低于左右两边的孩子只需分配一个糖果

评分相同的相邻孩子,分配的糖果可以不同

算法步骤如下:

1. 首先为每一个孩子分配1个糖果

记当前孩子序号为i,糖果数为candies[i],评分为ratings[i]

2. 从左向右遍历,若ratings[i] > ratings[i - 1],则令candies[i] = candies[i - 1] + 1

3. 从右向左遍历,若ratings[x] > ratings[x + 1],则令candies[x] = max(candies[x], candies[x + 1] + 1)

Python代码:

class Solution:
    # @param {integer[]} ratings
    # @return {integer}
    def candy(self, ratings):
        size = len(ratings)
        candies = [1] * size
        for x in range(1, size):
            if ratings[x] > ratings[x - 1]:
                candies[x] = candies[x - 1] + 1
        for x in range(size - 2, -1, -1):
            if ratings[x] > ratings[x + 1]:
                candies[x] = max(candies[x], candies[x + 1] + 1)
        return sum(candies)

 

本文链接:http://bookshadow.com/weblog/2015/08/06/leetcode-candy/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. Fivezh Fivezh 发布于 2016年3月25日 21:32 #

    2. 从左向右遍历,若ratings[i] > ratings[i - 1],则令candies[i] = candies[i] + 1
    应更正为:
    2. 从左向右遍历,若ratings[i] > ratings[i - 1],则令candies[i] = candies[i-1] + 1

  2. 在线疯狂 在线疯狂 发布于 2016年3月26日 09:37 #

    感谢更正,已经修改! :D

张贴您的评论