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?

题意

多个小朋友站成一排，根据他们的得分分发糖果，得分高的小朋友要比旁边得分低的小朋友得到的糖果多，每个小朋友至少得到一枚糖果，问最少要准备多少糖果？

思路

太简单了，略，时间复杂度是(O(2*n)=On)。空间上需要一个长度为n的数组，复杂度是O(n)。但是上次字节跳动版的改编题目不简单，他的小朋友不是站成一排而是一圈。有时间我会把这道题加到下面， tag

python实现

class Solution:    def candy(self, ratings):        n = len(ratings)        # print(n)        res = n * [1]        for i in range(1, n):            # print(i)            if ratings[i] > ratings[i - 1]:                res[i] = res[i-1] + 1        print(res)        for j in range(n-2, -1, -1):            # print(i)            if ratings[j] > ratings[j+1]:                res[j] = max(res[j+1] + 1, res[j])        print(res)        return sum(res)if __name__ == '__main__':    # a = [1, 2, 5, 5, 10]    # a = [1, 2]    a = [1, 0, 2]    so = Solution()    print(so.candy(a))

附加题

题意

多个小朋友站成一圈(第一个和第n个相连)，根据他们的得分分发糖果，得分高的小朋友要比旁边得分低的小朋友得到的糖果多，每个小朋友至少得到一枚糖果，问最少要准备多少糖果？

思路

其实也不难，就多一个开环的过程，但是当时脑袋短路了，写了一个小时

python实现

class Solution:    def candy(self, values, a):        # 开环        ratings = values + values        n = 2 * a        res = n * [1]        for i in range(1, n):            if ratings[i] > ratings[i - 1]:                res[i] = res[i-1] + 1        for j in range(n-2, -1, -1):            if ratings[j] > ratings[j+1]:                res[j] = max(res[j+1] + 1, res[j])        for i in range(a):            res[i] = max(res[i], res[i+a])        res = res[:a]        return sum(res)if __name__ == '__main__':    # a = [1, 2, 5, 7, 10]    # a = [1, 2, 5, 5, 10]    # a = [1, 2]    a = [1, 2, 3, 3]    so = Solution()    print(so.candy(a, len(a)))

转载地址：http://oejmb.baihongyu.com/

你可能感兴趣的文章