Java數據結構優先隊列實練
最後一塊石頭的重量
題目描述
思路詳解
這裡采用最大堆進行解題。
我們首先考慮,每次拿出兩個最大的進行比較,然後大的減去小的重新放入不就完成瞭嘛。
首先我們創建一個優先隊列,遍歷重量,放入隊列。依次取出重量最大的和第二大的,如果a>b就把a-b重新放入。直到隊列裡面的元素隻剩1個的時候,輸出結果。
代碼與結果
class Solution { public int lastStoneWeight(int[] stones) { PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a); for (int stone : stones) { pq.offer(stone); } while (pq.size() > 1) { int a = pq.poll(); int b = pq.poll(); if (a > b) { pq.offer(a - b); } } return pq.isEmpty() ? 0 : pq.poll(); } }
裝滿杯子需要的最短總時長
題目描述
思路詳解
這個題也是思考瞭很久。
分兩種情況:
第一種:很好想,有一種水特別多,那麼答案就是這種水的杯數。
第二種:就是一定可以匹配完成或者匹配到隻剩一杯。
我們隻需要先排序,在分情況就好。
代碼與結果
class Solution { public int fillCups(int[] amount) { Arrays.sort(amount); int sum=amount[0]+amount[1]+amount[2]; if(amount[1]+amount[0]>=amount[2]) sum=(sum+1)/2; else sum=amount[2]; return sum; } }
移除石子的最大得分
題目描述
思路詳解
本題的思路看起來簡單,也不是很好想。
我們先排一下序,兩種情況:
第一種:前兩個的和小於第三個,這時候我們一直拿最後一堆和任意一堆,結果就是a+b。
第二種: 前兩個數的和大於第三個數,那麼前兩堆一定可以內部抵消一部分。隻需總和除以2就好。
代碼與結果
class Solution { public int maximumScore(int a, int b, int c) { int[] arr = new int[] { a, b, c }; Arrays.sort(arr); a = arr[0]; b = arr[1]; c = arr[2]; if (a + b <= c) { return a + b; } else { return (a + b + c) / 2; } } }
到此這篇關於Java數據結構優先隊列實練的文章就介紹到這瞭,更多相關Java優先隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Java 數據結構之堆的概念與應用
- Java中PriorityQueue實現最小堆和最大堆的用法
- Java數據結構之堆(優先隊列)詳解
- Java中隊列Queue和Deque的區別與代碼實例
- Java 循環隊列/環形隊列的實現流程