Java數(shù)據(jù)結(jié)構(gòu)優(yōu)先隊列實練
最后一塊石頭的重量
題目描述
思路詳解
這里采用最大堆進行解題。
我們首先考慮,每次拿出兩個最大的進行比較,然后大的減去小的重新放入不就完成了嘛。
首先我們創(chuàng)建一個優(yōu)先隊列,遍歷重量,放入隊列。依次取出重量最大的和第二大的,如果a>b就把a-b重新放入。直到隊列里面的元素只剩1個的時候,輸出結(jié)果。
代碼與結(jié)果
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(); } }
裝滿杯子需要的最短總時長
題目描述
思路詳解
這個題也是思考了很久。
分兩種情況:
第一種:很好想,有一種水特別多,那么答案就是這種水的杯數(shù)。
第二種:就是一定可以匹配完成或者匹配到只剩一杯。
我們只需要先排序,在分情況就好。
代碼與結(jié)果
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; } }
移除石子的最大得分
題目描述
思路詳解
本題的思路看起來簡單,也不是很好想。
我們先排一下序,兩種情況:
第一種:前兩個的和小于第三個,這時候我們一直拿最后一堆和任意一堆,結(jié)果就是a+b。
第二種: 前兩個數(shù)的和大于第三個數(shù),那么前兩堆一定可以內(nèi)部抵消一部分。只需總和除以2就好。
代碼與結(jié)果
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; } } }
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)優(yōu)先隊列實練的文章就介紹到這了,更多相關(guān)Java優(yōu)先隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
redis scan命令導致redis連接耗盡,線程上鎖的解決
這篇文章主要介紹了redis scan命令導致redis連接耗盡,線程上鎖的解決,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-11-11Spring?BeanFactory容器的構(gòu)建和使用示例詳解
BeanFactory是Spring框架中的一部分,它提供了IoC(控制反轉(zhuǎn))的實現(xiàn)機制,下面小編就來和大家簡單聊聊BeanFactory容器的構(gòu)建和使用示例吧2023-07-07關(guān)于mybatis if else if 條件判斷SQL片段表達式取值和拼接問題
這篇文章主要介紹了mybatis if else if 條件判斷SQL片段表達式取值和拼接,文章通過自己真實使用的例子給大家詳細介紹,需要的朋友可以參考下2021-09-09intellij idea 2021.2 打包并上傳運行spring boot項目的詳細過程(spring boot 2
這篇文章主要介紹了intellij idea 2021.2 打包并上傳運行一個spring boot項目(spring boot 2.5.4),本文通過圖文并茂的形式給大家介紹的非常詳細,需要的朋友可以參考下2021-09-09javax.validation.constraints注解使用
這篇文章主要介紹了javax.validation.constraints注解使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-07-07Spring框架通過工廠創(chuàng)建Bean的三種方式實現(xiàn)
這篇文章主要介紹了Spring框架通過工廠創(chuàng)建Bean的三種方式實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-03-03IntelliJ IDEA中查看文件內(nèi)所有已聲明的方法(類似eclipse的outline)
今天小編就為大家分享一篇關(guān)于IntelliJ IDEA中查看文件內(nèi)所有已聲明的方法(類似eclipse的outline),小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2018-10-10