主題

LeetCode - 860. Lemonade Change 解題心得

Not In My Back Yard | 2021-01-28 00:00:03 | 巴幣 0 | 人氣 32

題目連結:


題目意譯:
在一個檸檬汽水攤販裡,每份檸檬汽水賣 5 元。

顧客們正排成一列等著購買你的汽水,且每人每次只買一份(以鈔票面額之序列表示)。

每位顧客只會買一份檸檬汽水且只會支付 5 、 10 或是 20 元的鈔票。你必須提供正確的零錢金額還給顧客,使得每位顧客的交易淨額為支付 5 元。

注意,你一開始手頭上沒有任何零錢。

回傳真(True)若且唯若你可以正確地找零錢給所有顧客。

注:
0 ≦ bills.length ≦ 10000
bills[i] 只會是 5 、 10 或是 20。



範例測資:
範例 1:
輸入: [5,5,5,10,20]
輸出: true
解釋:
從前三位顧客中,我們可以得到三張 5 元鈔票。
從第四位顧客裡,我們得到了一張 10 元鈔票並找一張 5 元。
從第五位顧客之中,我們找了一張 10 元以及一張 5 元的零錢。
因為所有顧客皆得到了正確的零錢,所以我們輸出真。

範例 2:
輸入: [5,5,10]
輸出: true

範例 3:
輸入: [10,10]
輸出: false

範例 4:
輸入: [5,5,10,10,20]
輸出: false
解釋:
從前兩位顧客,我們蒐集了兩張 5 元。
對於接著兩位顧客,我們每一人得到一張 10 元並退還一張 5 元。
對於最後一位顧客,我們無法給予 15 元的零錢,因為我們現在只剩下兩張 10 元。
因為並不是所有顧客都得到正確的零錢,因此答案為假(False)。


解題思維:
模擬即可。

一開始我們 5 元、10 元的零錢數都為 0 (分別命名為 C1 以及 C2)。

每當我們遇到有顧客支付 5 元時,因為恰好 5 元所以不需找零,而且 C1 的數量 + 1;
當顧客支付的是 10 元時,此時我們應找回 5 元,所以 C1 數量 - 1;
當顧客付 20 元,此時應找回 15 元,而 15 元有 10 + 5 與 5 + 5 + 5 兩種湊法,而我們應該優先使用 10 元(因為兩張 5 元可以充當一張 10 元),避免後面出錯。

如果找零錢時,有任何時刻面臨到無法正確找錢(如上的步驟),則回傳假。反之,如果都正確地找零了,則回傳真。




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

創作回應

更多創作