Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2022/12/28 09:23)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串156/719 (看更多)

1962. Remove Stones to Minimize the Total 給你一堆石頭，你每次可以從其中一堆移除floor(piles[i] / 2)個石頭，求出做了 n次操作後，這堆石頭最少還剩下幾個石頭。 Example: Input: piles = [5,4,9], k = 2 Output: 12 Explanation: 移除 piles[2]，piles = [5,4,5] 移除 pile[0]或piles[2]，piles = [3,4,5] or [5,4,3] 思路： 1.若要得到最少石頭，則我們每次都要從最大的石頭堆做移除，我們先用heap根據石頭數量進行排序，這樣每次pop出來都會是最大的一堆。 2.對heap做k次操作，每次pop操作完再把減少完的石頭push回去。 3.把heap的所有元素pop出來統計共有幾個石頭。 Java Code： ---------------------------------------- class Solution { public int minStoneSum(int[] piles, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder()); for (int pile : piles) { heap.offer(pile); } for (int i = 0; i < k; i++) { int top = heap.poll(); heap.offer(top - top/2); } int count = 0; while (!heap.isEmpty()) { count += heap.poll(); } return count; } } ---------------------------------------- 改良點：我們在放入heap的時候可以統計全部石頭共有幾個，在移除石頭的時候也可以統計被移除石頭的數量，最後兩者相減就可以不用把整個heap都再pop一次了。 Java Code： ---------------------------------------- class Solution { public int minStoneSum(int[] piles, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder()); int sum = 0; for (int pile : piles) { heap.offer(pile); sum += pile; } int removed = 0; for (int i = 0; i < k; i++) { int top = heap.poll(); removed += top/2; heap.offer(top - top/2); } return sum - removed; } } ---------------------------------------- -- https://i.imgur.com/fHpKflu.jpg