算法題--給小朋友發(fā)糖問題

image.png

0. 鏈接

題目鏈接

1. 題目

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?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

2. 思路1: 雙向加成法

  1. 基本思路是:
  • 首先初始化一個candies數(shù)組, 表示每個小孩分到的糖數(shù), 初始為1
  • 先自i=1開始從左到右遍歷ratings數(shù)組, 當(dāng)遇到ratings[i] > ratings[i - 1]蜈首,即遇到一個分?jǐn)?shù)比左邊鄰居高的小朋友時, 則 將他的糖數(shù)變?yōu)?code>max(candies[i], candies[i - 1] + 1), 確保他的糖比左邊小朋友多
  • 再從i = n - 2開始從右到左遍歷ratings數(shù)組, 當(dāng)遇到ratings[i] > ratings[i + 1]時, 即遇到一個分?jǐn)?shù)比右邊鄰居高的小朋友時, 則將他的糖數(shù)變?yōu)?code>max(candies[i], candies[i + 1] + 1), 確保他的糖同時也比右邊的鄰居多
  1. 分析:
  • 對于每個節(jié)點, 都要遍歷2遍 因此時間復(fù)雜度為O(n), 空間復(fù)雜度為O(n)
  1. 復(fù)雜度
  • 時間復(fù)雜度 O(n)
  • 空間復(fù)雜度 O(n)

3. 代碼

# coding:utf8
from typing import List


class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        if n == 0:
            return 0

        candies = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                new_num = max(candies[i], candies[i - 1] + 1)
                candies[i] = new_num
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                new_num = max(candies[i], candies[i + 1] + 1)
                candies[i] = new_num

        return sum(candies)


def my_test(solution, ratings):
    print('input: ratings={}; output: {}'.format(ratings, solution.candy(ratings)))


solution = Solution()

my_test(solution, [1, 0, 2])
my_test(solution, [1, 2, 2])
my_test(solution, [2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0])

輸出結(jié)果

input: ratings=[1, 0, 2]; output: 5
input: ratings=[1, 2, 2]; output: 4
input: ratings=[2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0]; output: 21

4. 結(jié)果

image.png

5. 思路2: 曲線法

  1. 過程
  • 增加up, down, peak赏淌, 從左到右只遍歷1次
  • up表示當(dāng)前ratings連續(xù)上升的步數(shù), down表示當(dāng)前ratings連續(xù)下降的步數(shù), peak表示最近的1次連續(xù)上升階段的步數(shù)
  • 關(guān)于發(fā)糖的問題六水,可以換個角度來看待掷贾,即如果將ratings值隨下標(biāo)的變化想帅,看做一個曲線的話,這個曲線可以看成是若干個連續(xù)上升的上坡旨剥、若干個平坡轨帜、若干個下坡構(gòu)成蚌父;
  • 當(dāng)處于上坡階段時梢什,我們給第一步的小孩先發(fā)1顆糖嗡午, 輪到給第二個小朋友發(fā)的時候荔睹,就不能只發(fā)1顆糖了僻他,因為他比第一個小朋友rating高, 所以給他發(fā)2顆糖腊尚,依次類推婿斥,給第up個小朋友民宿,就發(fā)up顆糖, 順便更新下peak活鹰,表示連續(xù)up的步數(shù)
  • 當(dāng)處于平坡的時候志群,意味著只需要給小孩發(fā)1顆糖就好了赖舟,因為他沒有超過他左邊鄰居的rating值嘛, 另外peak也重置為1
  • 當(dāng)處于下坡的時候宾抓,此時第一個處于下坡的小孩,要發(fā)的糖數(shù)要分情況對待紧显,
    • 當(dāng)down < peak時缕棵,即當(dāng)前是從一個峰值直接轉(zhuǎn)而下跌招驴,則只需要給這個小孩發(fā)1顆糖,同時遞增down别厘;同理触趴,當(dāng)遇到下坡第2個小孩的時候冗懦,給他發(fā)1顆糖的同時披蕉,要給第1個小孩再補一顆糖没讲,這一步要發(fā)出去2顆糖食零;遇到下坡第3個小孩的時候贰谣,給他發(fā)1顆糖的同時吱抚,要給前2個小孩各多發(fā)1顆糖秘豹,這次發(fā)出去3顆糖;可以看出在下坡第down步的時候涮坐,發(fā)出去down顆糖
    • 當(dāng)down >= peak時, 表示當(dāng)前已經(jīng)下坡太多步了,此時下坡處第1個小孩的數(shù)量捷雕,已經(jīng)趕上了峰值處小孩的糖數(shù)量壹甥,為了保持峰值小孩的糖數(shù)量處于優(yōu)勢句柠,從當(dāng)前到以后每下坡1步,都要額外給峰值小孩補1顆糖缸榄,所以每步發(fā)出去down + 1顆糖
  • 將匯總的發(fā)糖數(shù)candies返回即可
  1. 分析
    利用此法, 在兩個指針startend的幫助下甚带,每個節(jié)點只被遍歷1次鹰贵,就得出了結(jié)論碉输,時間復(fù)雜度降低到了O(n), 空間復(fù)雜度仍然是O(1)
  2. 時間復(fù)雜度 O(n)
  3. 空間復(fù)雜度 O(1)

6. 代碼

# coding:utf8
from typing import List


class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        if n <= 1:
            return n

        up = 1
        peak = up
        down = 0
        candies = 1
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                up += 1
                peak = up
                down = 0
                candies += up
            elif ratings[i] < ratings[i - 1]:
                up = 1
                down += 1
                candies += down if down < peak else down + 1
            else:
                up = 1
                down = 0
                peak = up
                candies += 1

        return candies


def my_test(solution, ratings):
    print('input: ratings={}; output: {}'.format(ratings, solution.candy(ratings)))


solution = Solution()

my_test(solution, [1, 0, 2])
my_test(solution, [1, 2, 2])
my_test(solution, [2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0])

輸出結(jié)果

input: ratings=[1, 0, 2]; output: 5
input: ratings=[1, 2, 2]; output: 4
input: ratings=[2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0]; output: 21

7. 結(jié)果

image.png
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末阻荒,一起剝皮案震驚了整個濱河市侨赡,隨后出現(xiàn)的幾起案子羊壹,更是在濱河造成了極大的恐慌舶掖,老刑警劉巖眨攘,帶你破解...
    沈念sama閱讀 222,865評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件共螺,死亡現(xiàn)場離奇詭異藐不,居然都是意外死亡雏蛮,警方通過查閱死者的電腦和手機(jī)挑秉,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,296評論 3 399
  • 文/潘曉璐 我一進(jìn)店門犀概,熙熙樓的掌柜王于貴愁眉苦臉地迎上來姻灶,“玉大人产喉,你說我怎么就攤上這事镊叁』奁” “怎么了互广?”我有些...
    開封第一講書人閱讀 169,631評論 0 364
  • 文/不壞的土叔 我叫張陵,是天一觀的道長尤莺。 經(jīng)常有香客問我颤霎,道長友酱,這世上最難降的妖魔是什么缔杉? 我笑而不...
    開封第一講書人閱讀 60,199評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮霸琴,結(jié)果婚禮上梧乘,老公的妹妹穿的比我還像新娘勋乾。我一直安慰自己辑莫,他們只是感情好各吨,可當(dāng)我...
    茶點故事閱讀 69,196評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著屉更,像睡著了一般瑰谜。 火紅的嫁衣襯著肌膚如雪萨脑。 梳的紋絲不亂的頭發(fā)上渤早,一...
    開封第一講書人閱讀 52,793評論 1 314
  • 那天鹊杖,我揣著相機(jī)與錄音仅淑,去河邊找鬼涯竟。 笑死庐船,一個胖子當(dāng)著我的面吹牛筐钟,可吹牛的內(nèi)容都是我干的篓冲。 我是一名探鬼主播壹将,決...
    沈念sama閱讀 41,221評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼妇菱,長吁一口氣:“原來是場噩夢啊……” “哼暴区!你這毒婦竟也來了仙粱?” 一聲冷哼從身側(cè)響起伐割,我...
    開封第一講書人閱讀 40,174評論 0 277
  • 序言:老撾萬榮一對情侶失蹤负溪,失蹤者是張志新(化名)和其女友劉穎川抡,沒想到半個月后崖堤,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體密幔,經(jīng)...
    沈念sama閱讀 46,699評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡昧廷,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,770評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,918評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出姥宝,到底是詐尸還是另有隱情伶授,我是刑警寧澤,帶...
    沈念sama閱讀 36,573評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站茸炒,受9級特大地震影響壁公,放射性物質(zhì)發(fā)生泄漏紊册。R本人自食惡果不足惜囊陡,卻給世界環(huán)境...
    茶點故事閱讀 42,255評論 3 336
  • 文/蒙蒙 一妥色、第九天 我趴在偏房一處隱蔽的房頂上張望遏片。 院中可真熱鬧,春花似錦丁稀、人聲如沸吼拥。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,749評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽凿可。三九已至,卻和暖如春授账,著一層夾襖步出監(jiān)牢的瞬間枯跑,已是汗流浹背白热。 一陣腳步聲響...
    開封第一講書人閱讀 33,862評論 1 274
  • 我被黑心中介騙來泰國打工敛助, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人屋确。 一個月前我還...
    沈念sama閱讀 49,364評論 3 379
  • 正文 我出身青樓纳击,卻偏偏與公主長得像,于是被迫代替她去往敵國和親攻臀。 傳聞我的和親對象是個殘疾皇子焕数,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,926評論 2 361