主題

LeetCode - 1103. Distribute Candies to People 解題心得

Not In My Back Yard | 2021-03-23 00:00:06 | 巴幣 0 | 人氣 62

題目連結:


題目意譯:
我們分配一些糖果 candies,到一列有 n = num_people 個人手上,其以下列方式:
我們給 1 個糖果到第一個人手上、2 個糖果到第二個人手上,以此類推直到我們給 n 個糖果到最後一個人手上。

然後我們回到列的開頭,n + 1 個糖果給第一個人、 n + 2 個糖果給第二個人,以此類推直到我們給 2n 個糖果到最後一個人手上。

這個過程會一直重複(每次給的糖果數增加一個,且移回到列的開頭於我們抵達列的尾端後)直到我們糖果發完為止。停止前的最後一個人將接受到我們剩下的所有糖果(不一定比給前一個人的多一個)

回傳一個陣列(其長度為 num_people 且數字總和為 candies)代表著糖果最後的分配情況。

限制:
1 ≦ candies ≦ 10 ^ 9
1 ≦ num_people ≦ 1000



範例測資:
範例 1:
輸入: candies = 7, num_people = 4
輸出: [1,2,3,1]
解釋:
第一回中,ans[0] += 1 而陣列為 [1,0,0,0]。
第二回中,ans[1] += 2 而陣列為 [1,2,0,0]。
第三回中,ans[2] += 3 而陣列為 [1,2,3,0]。
第四回中,ans[3] += 1 (因為只剩一個糖果)而最終陣列為 [1,2,3,1]。

範例 2:
輸入: candies = 10, num_people = 3
輸出: [5,2,3]
解釋:
第一回中,ans[0] += 1 而陣列為 [1,0,0]。
第二回中,ans[1] += 2 而陣列為 [1,2,3]。
第三回中,ans[2] += 3 而陣列為 [1,2,3]。
第四回中,ans[0] += 4 而最終陣列為 [5,2,3]。


解題思維:
模擬即可。

就是按照題目的規則去跑:用兩個變數,一個控制現在要給的人 P、一個是給的糖果數量 C。然後就一直 ans[P] += C 、 P += 1 、 C += 1 。

當 P = n 時,代表碰到了結尾所以把 P 設為 0,讓它回到原點。



不過也可以用計算的,先計算它會跑滿幾輪。然後就直接只掃一、兩趟就把 ans[] 值設定為最終值(記得考慮除了跑滿的那幾輪還有最後一輪,該輪可能中途就停下了)。

但是這樣不會比模擬快上多少,就算是 10 ^ 9 個糖果,當 C 為四萬五左右總共送出的糖果數就超過該數了。所以本題可以直接模擬,而不用額外計算輪數。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作