前往
大廳
主題

LeetCode - 1046. Last Stone Weight 解題心得

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

題目連結:


題目意譯:
我們有著一些石頭,每個石頭有著正整數重量值。

每回合,我們選擇兩顆最重的石頭將它們砸向彼此。假設兩石頭重為 x 和 y 且 x ≦ y。碰撞之結果為:
如果 x == y,則兩顆石頭完全摧毀。
如果 x != y,則重 x 的石頭完全摧毀而重 y 之石頭變為重 y - x。

最終,最多只會有一個石頭留下來。回傳該石頭之重量(或是 0 ,如果沒有任何石頭留下)。

注:
1 ≦ stones.length ≦ 30
1 ≦ stones[i] ≦ 1000



範例測資:
輸入: [2,7,4,1,8,1]
輸出: 1
解釋:
我們合併 7 和 8 而得到 1,所以陣列變為 [2,4,1,1,1],然後
我們合併 2 和 4 而得到 2,所以陣列變為 [2,1,1,1],然後
我們合併 2 和 1 而得到 1,所以陣列變為 [1,1,1],然後
我們合併 1 和 1 而得到 0,所以陣列變為 [1],然後該值就是最後石頭之重量。


解題思維:
用一個優先佇列(Priority Queue)PQ 把石頭的重量儲存起來。而優先佇列的特性就是可以快速得到其中的極值(例如在本題中是最大值)。

所以每次就是從 PQ 中取出兩個重量值,判斷有沒有一樣,一樣就忽略;反之,將大的值減去小的值然後將新值放入 P 中。重複此步驟直到 P 的元素不足兩個。

最後看 P 是否為空。空的話,回傳 0;反之,回傳剩下的那顆石頭之重量值。




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

創作回應

更多創作