資訊專欄INFORMATION COLUMN
摘要：題目要求假設(shè)有個(gè)孩子站成一排，每個(gè)孩子擁有一個(gè)評(píng)估值。我們可以觀察到，每次最遠(yuǎn)只需要額外分發(fā)到距離當(dāng)前最近的評(píng)分最高的那個(gè)孩子。因?yàn)樗奶枪麛?shù)量的增加并不會(huì)影響到之前孩子。當(dāng)有多個(gè)最近評(píng)分最高的孩子時(shí)，則選擇最后一個(gè)。
題目要求
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?
假設(shè)有N個(gè)孩子站成一排，每個(gè)孩子擁有一個(gè)評(píng)估值。現(xiàn)在要根據(jù)以下的需求給孩子們分發(fā)糖果：
每個(gè)孩子至少有一顆糖
有更高評(píng)估值的孩子應(yīng)當(dāng)比兩側(cè)孩子得到的糖更多
問(wèn)最少要發(fā)出多少顆糖？
思路和代碼這里我們可以舉一個(gè)例子來(lái)先試著分配一下：
假設(shè)有10個(gè)孩子，每個(gè)孩子對(duì)應(yīng)的評(píng)估分別是[3,4,5,7,2,3,3,2,1,10]
按照盡量少分配的原則，前四個(gè)孩子我們會(huì)分別給1，2，3，4顆糖，從第五個(gè)孩子開(kāi)始，我們只需要給1顆糖就可以滿足需求。
前五個(gè)孩子的分配情況如下：
[1,2,3,4,1, , , , , ]
第六個(gè)孩子和第七個(gè)孩子評(píng)估值相同，我們還是可以將第七個(gè)孩子賦值1，因?yàn)檫@樣還是可以滿足要求。結(jié)果如下：
[1,2,3,4,1,2,1, , , ]
到第八個(gè)孩子的時(shí)候，我們發(fā)現(xiàn)這個(gè)孩子評(píng)估值比第七個(gè)孩子低，但是基于每個(gè)孩子最少一顆糖的原理，我們必須給第八個(gè)孩子一顆糖并且開(kāi)始回調(diào)前面分發(fā)的糖的數(shù)量。
[1,2,3,4,1,2,2,1, , ]
第九個(gè)孩子的情況一樣，我們同樣給他一顆糖并調(diào)整：
[1,2,3,4,1,2,3,2,1, ]
最后孩子評(píng)分比前一個(gè)評(píng)分高，我們只需直接在前一個(gè)孩子的數(shù)量上加1即可：
[1,2,3,4,1,2,3,2,1,2]
由此我們可以總結(jié)出以下幾個(gè)結(jié)論：
當(dāng)后一個(gè)孩子比前一個(gè)孩子評(píng)分高時(shí)，直接在前一個(gè)孩子糖果數(shù)量基礎(chǔ)上加1
當(dāng)后一個(gè)孩子比前一個(gè)孩子評(píng)分低時(shí)
前一個(gè)孩子糖果數(shù)量大于1，則該孩子糖果數(shù)量為1
前一個(gè)孩子糖果數(shù)量為1，則該孩子糖果數(shù)量為1，并且將前面相應(yīng)孩子的糖果數(shù)量加1
當(dāng)后一個(gè)孩子和前一個(gè)孩子評(píng)分一樣多，則該孩子糖果數(shù)量為1
這是我們只需要知道，當(dāng)后一個(gè)孩子比前一個(gè)孩子評(píng)分低，且前一個(gè)孩子糖果數(shù)量為1時(shí)，最少由多少個(gè)孩子需要額外分發(fā)一個(gè)糖果。我們可以觀察到，每次最遠(yuǎn)只需要額外分發(fā)到距離當(dāng)前最近的評(píng)分最高的那個(gè)孩子。因?yàn)樗奶枪麛?shù)量的增加并不會(huì)影響到之前孩子。
至于該評(píng)分最高的孩子是否需要增加糖果，則要看后面的孩子增加后的糖果數(shù)量是不是比他高。
當(dāng)有多個(gè)最近評(píng)分最高的孩子時(shí)，則選擇最后一個(gè)。
代碼如下：
public int candy(int[] ratings) {
int count = 1;
int summitIndex = 0;
int summitCandy = 1;
int prevCandy = 1;
for(int i = 1 ; i ratings[i-1]){
prevCandy++;
count += prevCandy;
summitIndex = i;
summitCandy = prevCandy;
}else if(ratings[i] < ratings[i-1]){
if(prevCandy == 1){
count += (i - summitIndex) + (i-summitIndex >= summitCandy ? 1 : 0);
}else{
prevCandy = 1;
count += prevCandy;
}
}else{
prevCandy = 1;
count += prevCandy;
summitIndex = i;
summitCandy = prevCandy;
}
}
return count;
}
想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/68610.html
摘要：今日題目老師想給孩子們分發(fā)糖果，有個(gè)孩子站成了一條直線，老師會(huì)根據(jù)每個(gè)孩子的表現(xiàn)，預(yù)先給他們?cè)u(píng)分。相鄰的孩子中，評(píng)分高的孩子必須獲得更多的糖果。示例輸入輸出解釋你可以分別給這三個(gè)孩子分發(fā)顆糖果。第三個(gè)孩子只得到顆糖果，這已滿足上述兩個(gè)條件。 今日題目 老師想給孩子們分發(fā)糖果，有N個(gè)孩子站成了一條直線，老師會(huì)根據(jù)每個(gè)孩子的表現(xiàn)，預(yù)先給他們?cè)u(píng)分。你需要按照以下要求，幫助老師給這些孩子分發(fā)糖...
摘要：貪心法復(fù)雜度時(shí)間空間思路典型的貪心法，如果一個(gè)孩子比另一個(gè)孩子的分高，我們只多給塊糖。我們可以先從左往右遍歷，確保每個(gè)孩子根他左邊的孩子相比，如果分高，則糖要多個(gè)，如果分比左邊低，就只給一顆。 Candy There are N children standing in a line. Each child is assigned a rating value. You are gi...
摘要：保證高的小朋友拿到的糖果更多，我們建立一個(gè)分糖果數(shù)組。首先，分析邊界條件如果沒(méi)有小朋友，或者只有一個(gè)小朋友，分別對(duì)應(yīng)沒(méi)有糖果，和有一個(gè)糖果。排排坐，吃果果。先往右，再往左。右邊高，多一個(gè)。總和加上小朋友總數(shù)，就是要準(zhǔn)備糖果的總數(shù)啦。 Problem There are N children standing in a line. Each child is assigned a rat...
Problem Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribu...
摘要：買糖果題目來(lái)源京東實(shí)習(xí)生招聘原題鏈接可在線提交賽碼網(wǎng)問(wèn)題描述某糖果公司專門生產(chǎn)兒童糖果，它最受兒童歡迎的糖果有兩個(gè)序列，均采用盒式包裝。小東希望你能幫她解決這一問(wèn)題。 最近比較忙，又有一段時(shí)間沒(méi)寫(xiě)題目了，終于在前幾天把賽碼網(wǎng)上，JD的2016秋招和2017實(shí)習(xí)生招聘剩下的4星難度題目做了，至此所有4星難度題目都解決了，5星難度題目還剩下一個(gè)應(yīng)該是計(jì)算幾何學(xué)的題目，因?yàn)檫@塊我不熟悉，后面...
閱讀 4996·2021-09-22 14:57
閱讀 622·2019-08-30 15:56
閱讀 2718·2019-08-30 15:53
閱讀 2295·2019-08-29 14:15
閱讀 1738·2019-08-28 17:54
閱讀 610·2019-08-26 13:37
閱讀 3540·2019-08-26 10:57
閱讀 1106·2019-08-26 10:32
