【LeetCode】貪心算法--分發糖果（135）

劉永祥發布于2019-07-30 18:46 / 1892人閱讀

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

今日題目

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

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

題目分析

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

代碼實現

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)

寫在最后

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

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

GPU云服務器云服務器貪心算法的題目貪心算法java找零最簡單的貪心算法最小集合覆蓋貪心算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43021.html

【LeetCode】貪心算法--劃分字母區間（763）

摘要：寫在前面今天這篇文章是貪心算法系列的第三篇劃分字母區間。前文回顧貪心算法分發糖果刷題匯總匯總貼今日題目字符串由小寫字母組成。返回一個表示每個字符串片段的長度的列表。示例輸入輸出解釋劃分結果為。每個字母最多出現在一個片段中。寫在前面今天這篇文章是貪心算法系列的第三篇--劃分字母區間。前文回顧：【LeetCode】貪心算法--分發糖果（135）刷題匯總：【LeetCode】匯總...

honhon 2019-07-31 11:21 評論0 收藏0
leetcode135. Candy

摘要：題目要求假設有個孩子站成一排，每個孩子擁有一個評估值。我們可以觀察到，每次最遠只需要額外分發到距離當前最近的評分最高的那個孩子。因為他的糖果數量的增加并不會影響到之前孩子。當有多個最近評分最高的孩子時，則選擇最后一個。題目要求 There are N children standing in a line. Each child is assigned a rating value....

shmily 2019-08-15 14:26 評論0 收藏0
[Leetcode] Candy 分糖果

摘要：貪心法復雜度時間空間思路典型的貪心法，如果一個孩子比另一個孩子的分高，我們只多給塊糖。我們可以先從左往右遍歷，確保每個孩子根他左邊的孩子相比，如果分高，則糖要多個，如果分比左邊低，就只給一顆。 Candy There are N children standing in a line. Each child is assigned a rating value. You are gi...

張憲坤 2019-08-14 12:40 評論0 收藏0
【LeetCode】貪心算法--買賣股票的最佳時機 II（122）

摘要：貪心算法每一步必須滿足一下條件可行的即它必須滿足問題的約束。四題目分析貪心算法，總是做出在當前看來是最好的選擇，不從整體最優上加以考慮，也就是說，只關心當前最優解，按照貪心策略，不關心以后，我們只關心當前利益。一、寫在前面為什么要在LeetCode刷題？大家都知道不管是校招還是社招算法題是必考題，而這一部分恰巧是大多數人的短板，所以刷題首先是為了提高自身的編程能力，能夠在算法面試中...

xbynet 2019-07-31 11:21 評論0 收藏0
LeetCode——Longest Substring Without Repeating Char

摘要：原問題我的沙雕解法無重復字母存在重復字母挨打最暴力的無腦解法，耗時。。。原問題 Given a string, find the length of the?longest substring?without repeating characters. Example 1: Input: abcabcbb Output: 3 Explanation: The answer is a...

forsigner 2019-08-26 13:31 評論0 收藏0