leetcode135. Candy

shmily 發布于2019-08-15 14:26 / 3002人閱讀

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

題目要求

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?

假設有N個孩子站成一排，每個孩子擁有一個評估值。現在要根據以下的需求給孩子們分發糖果：

每個孩子至少有一顆糖

有更高評估值的孩子應當比兩側孩子得到的糖更多

問最少要發出多少顆糖？

思路和代碼

這里我們可以舉一個例子來先試著分配一下：
假設有10個孩子，每個孩子對應的評估分別是[3,4,5,7,2,3,3,2,1,10]
按照盡量少分配的原則，前四個孩子我們會分別給1，2，3，4顆糖，從第五個孩子開始，我們只需要給1顆糖就可以滿足需求。

前五個孩子的分配情況如下：
[1,2,3,4,1, , , , , ]

第六個孩子和第七個孩子評估值相同，我們還是可以將第七個孩子賦值1，因為這樣還是可以滿足要求。結果如下：
[1,2,3,4,1,2,1, , , ]

到第八個孩子的時候，我們發現這個孩子評估值比第七個孩子低，但是基于每個孩子最少一顆糖的原理，我們必須給第八個孩子一顆糖并且開始回調前面分發的糖的數量。
[1,2,3,4,1,2,2,1, , ]

第九個孩子的情況一樣，我們同樣給他一顆糖并調整：
[1,2,3,4,1,2,3,2,1, ]

最后孩子評分比前一個評分高，我們只需直接在前一個孩子的數量上加1即可：
[1,2,3,4,1,2,3,2,1,2]

由此我們可以總結出以下幾個結論：

當后一個孩子比前一個孩子評分高時，直接在前一個孩子糖果數量基礎上加1

當后一個孩子比前一個孩子評分低時

前一個孩子糖果數量大于1，則該孩子糖果數量為1

前一個孩子糖果數量為1，則該孩子糖果數量為1，并且將前面相應孩子的糖果數量加1

當后一個孩子和前一個孩子評分一樣多，則該孩子糖果數量為1

這是我們只需要知道，當后一個孩子比前一個孩子評分低，且前一個孩子糖果數量為1時，最少由多少個孩子需要額外分發一個糖果。我們可以觀察到，每次最遠只需要額外分發到距離當前最近的評分最高的那個孩子。因為他的糖果數量的增加并不會影響到之前孩子。
至于該評分最高的孩子是否需要增加糖果，則要看后面的孩子增加后的糖果數量是不是比他高。

當有多個最近評分最高的孩子時，則選擇最后一個。

代碼如下：

    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;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Candy 135郵箱 135cdn Leetcod

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

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

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

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

劉永祥 2019-07-30 18:46 評論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
[LintCode/LeetCode] Candy

摘要：保證高的小朋友拿到的糖果更多，我們建立一個分糖果數組。首先，分析邊界條件如果沒有小朋友，或者只有一個小朋友，分別對應沒有糖果，和有一個糖果。排排坐，吃果果。先往右，再往左。右邊高，多一個。總和加上小朋友總數，就是要準備糖果的總數啦。 Problem There are N children standing in a line. Each child is assigned a rat...

baishancloud 2019-08-14 15:43 評論0 收藏0
[LeetCode] 575. Distribute Candies

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...

djfml 2019-08-16 13:47 評論0 收藏0
京東實習生招聘題目解析(二)

摘要：買糖果題目來源京東實習生招聘原題鏈接可在線提交賽碼網問題描述某糖果公司專門生產兒童糖果，它最受兒童歡迎的糖果有兩個序列，均采用盒式包裝。小東希望你能幫她解決這一問題。最近比較忙，又有一段時間沒寫題目了，終于在前幾天把賽碼網上，JD的2016秋招和2017實習生招聘剩下的4星難度題目做了，至此所有4星難度題目都解決了，5星難度題目還剩下一個應該是計算幾何學的題目，因為這塊我不熟悉，后面...

UnixAgain 2019-07-30 14:27 評論0 收藏0