【LeetCode】貪心算法--分發(fā)糖果（135）

劉永祥發(fā)布于2019-07-30 18:46 / 1898人閱讀

摘要：今日題目老師想給孩子們分發(fā)糖果，有個孩子站成了一條直線，老師會根據(jù)每個孩子的表現(xiàn)，預(yù)先給他們評分。相鄰的孩子中，評分高的孩子必須獲得更多的糖果。示例輸入輸出解釋你可以分別給這三個孩子分發(fā)顆糖果。第三個孩子只得到顆糖果，這已滿足上述兩個條件。

今日題目

老師想給孩子們分發(fā)糖果，有N個孩子站成了一條直線，老師會根據(jù)每個孩子的表現(xiàn)，預(yù)先給他們評分。
你需要按照以下要求，幫助老師給這些孩子分發(fā)糖果：
每個孩子至少分配到 1 個糖果。相鄰的孩子中，評分高的孩子必須獲得更多的糖果。那么這樣下來，老師至少需要準(zhǔn)備多少顆糖果呢？

示例 1:
輸入: [1,0,2]
輸出: 5
解釋: 你可以分別給這三個孩子分發(fā) 2、1、2 顆糖果。
示例 2:
輸入: [1,2,2]
輸出: 4
解釋: 你可以分別給這三個孩子分發(fā) 1、2、1 顆糖果。第三個孩子只得到 1 顆糖果，這已滿足上述兩個條件。

題目分析

對于這個問題，主要的條件是要相鄰孩子，得分高的拿的糖果要多（不包括相等得分），還有就是每個人最少都要有一個。
解決這個問題我們還是采用貪心算法，首先初始化每個人分配的糖果數(shù)量都是1，然后這個算法需要遍歷兩遍，第一遍從左往右遍歷，如果當(dāng)前孩子的分?jǐn)?shù)大于前一個孩子的分?jǐn)?shù)，則當(dāng)前孩子得到的糖果在前一個孩子的基礎(chǔ)上加1；然后，第二遍從右往左遍歷，如果當(dāng)前孩子的分?jǐn)?shù)大于他右邊孩子的分?jǐn)?shù)，并且他的糖果不比他右邊孩子多，則糖果數(shù)在他基礎(chǔ)上加1；最后，將所有孩子的糖果數(shù)相加即可。
第二次遍歷是為了處理數(shù)組中降序和有出現(xiàn)相鄰孩子分?jǐn)?shù)相同的情況。

代碼實(shí)現(xiàn)

class Solution:

def candy(self, ratings):
   """
   :type ratings: List[int]
   :rtype: int
    """
   num = [1]*len(ratings)
   for i in range(0,len(ratings)-1):
   if ratings[i+1] > ratings[i]:
       num[i+1] = num[i] + 1     
   for i in range(len(ratings)-1,0,-1):
       if ratings[i] < ratings[i-1]:
           num[i-1] = max(num[i]+1,num[i-1])

   return sum(num)

寫在最后

寒假已經(jīng)跟一個小伙伴商量好一起刷題，感興趣的小伙伴也可以加入我們，希望大家每天可以交流刷題的心得，為了保證質(zhì)量我會控制人數(shù)，大約在12人左右。

推薦閱讀：
Python騷操作 | 用Python來P圖