摘要:貪心法復雜度時間空間思路典型的貪心法,如果一個孩子比另一個孩子的分高,我們只多給塊糖。我們可以先從左往右遍歷,確保每個孩子根他左邊的孩子相比,如果分高,則糖要多個,如果分比左邊低,就只給一顆。
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(N) 空間 O(N)
思路典型的貪心法,如果一個孩子比另一個孩子的分高,我們只多給1塊糖。我們可以先從左往右遍歷,確保每個孩子根他左邊的孩子相比,如果分高,則糖要多1個,如果分比左邊低,就只給一顆。然后我們再從右往左遍歷,確保每個孩子跟他右邊的孩子相比,如果分高則糖至少多1個(這里至少多1個的意思是,我們要取當前孩子手里糖的數量,和其右邊孩子糖的數量加1,兩者的較大值)。
代碼public class Solution { public int candy(int[] ratings) { if(ratings.length <= 1){ return ratings.length; } int[] candies = new int[ratings.length]; candies[0] = 1; // 先從左往右分糖,分數較高的多拿一顆糖,分數較少的只拿一顆糖 for(int i = 1; i < ratings.length; i++){ if(ratings[i] > ratings[i - 1]){ candies[i] = candies[i - 1] + 1; } else { candies[i] = 1; } } int sum = candies[candies.length - 1]; // 再從右往左繼續分糖,分數較高的確保比右邊多一顆就行了 for(int i = ratings.length - 2; i >= 0; i--){ if(ratings[i] > ratings[i + 1]){ candies[i] = Math.max(candies[i + 1] + 1, candies[i]); } sum += candies[i]; } return sum; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/64629.html
摘要:保證高的小朋友拿到的糖果更多,我們建立一個分糖果數組。首先,分析邊界條件如果沒有小朋友,或者只有一個小朋友,分別對應沒有糖果,和有一個糖果。排排坐,吃果果。先往右,再往左。右邊高,多一個。總和加上小朋友總數,就是要準備糖果的總數啦。 Problem There are N children standing in a line. Each child is assigned a rat...
摘要:題目要求假設有個孩子站成一排,每個孩子擁有一個評估值。我們可以觀察到,每次最遠只需要額外分發到距離當前最近的評分最高的那個孩子。因為他的糖果數量的增加并不會影響到之前孩子。當有多個最近評分最高的孩子時,則選擇最后一個。 題目要求 There are N children standing in a line. Each child is assigned a rating value....
摘要:今日題目老師想給孩子們分發糖果,有個孩子站成了一條直線,老師會根據每個孩子的表現,預先給他們評分。相鄰的孩子中,評分高的孩子必須獲得更多的糖果。示例輸入輸出解釋你可以分別給這三個孩子分發顆糖果。第三個孩子只得到顆糖果,這已滿足上述兩個條件。 今日題目 老師想給孩子們分發糖果,有N個孩子站成了一條直線,老師會根據每個孩子的表現,預先給他們評分。你需要按照以下要求,幫助老師給這些孩子分發糖...
摘要:買糖果題目來源京東實習生招聘原題鏈接可在線提交賽碼網問題描述某糖果公司專門生產兒童糖果,它最受兒童歡迎的糖果有兩個序列,均采用盒式包裝。小東希望你能幫她解決這一問題。 最近比較忙,又有一段時間沒寫題目了,終于在前幾天把賽碼網上,JD的2016秋招和2017實習生招聘剩下的4星難度題目做了,至此所有4星難度題目都解決了,5星難度題目還剩下一個應該是計算幾何學的題目,因為這塊我不熟悉,后面...
摘要:純函數式狀態隨機數生成器很明顯,原有的函數不是引用透明的,這意味著它難以被測試組合并行化。售貨機在輸出糖果時忽略所有輸入本章知識點惰性求值函數式狀態 第二節?惰性求值與函數式狀態 在下面的代碼中我們對List數據進行了一些處理 List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3) 考慮一下這段程序是如何求值的,如果我們跟蹤一下...
閱讀 1487·2021-10-14 09:43
閱讀 1453·2021-10-09 09:58
閱讀 1946·2021-09-28 09:42
閱讀 3737·2021-09-26 09:55
閱讀 1763·2021-08-27 16:23
閱讀 2765·2021-08-23 09:46
閱讀 915·2019-08-30 15:55
閱讀 1432·2019-08-30 15:54