LeetCode1046 最后一块石头的重量(贪心—Java优先队列简单应用)
2024-09-02 12:51:52
题目:
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出两块最重的石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。
提示:
1 <= stones.length <= 30
1 <= stones[i] <= 1000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/last-stone-weight
思路:
利用优先队列,每次弹出数组中最大的两个数字,然后用大数减去小数,结果放回优先队列,直到优先队列中只剩下一个元素为止,这个元素的值就是最终的结果。
代码:
import java.util.*;
import java.math.*; class Solution {
static Comparator<Integer> cmp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
};
public int lastStoneWeight(int[] stones) {
Queue<Integer> queue = new PriorityQueue<>(cmp);
for(int i=0; i<stones.length; i++){
queue.add(stones[i]);
}
while(queue.size() > 1){
int a = queue.poll();
int b = queue.poll();
//System.out.println(a+" "+b);
queue.add(Math.max(a,b) - Math.min(a,b));
}
return queue.poll();
}
} public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Solution solution = new Solution();
int n = scanner.nextInt();
int[] chips = new int[n];
for(int i=0; i<n; i++){
chips[i] = scanner.nextInt();
}
System.out.println(solution.lastStoneWeight(chips));
}
}
感谢博友的博客内容,参考Java优先队列的应用:
https://www.cnblogs.com/wei-jing/p/10806236.html
最新文章
- 在VMware下正确克隆CentOS6.5的打开方式
- Asp.net MVC使用Filter解除Session, Cookie等依赖
- 隐藏路由器的WIFI信号,防蹭网
- 9.装饰者模式(Decorator Pattern)
- mvc存储Cookie和读取Cookie方法
- JavaScript获取和设置CheckBox状态
- php 实现同一个账号同时只能一个人登录
- Hibernate防止SQL注入
- 关于split与StringTokenizer的理解
- python3[爬虫实战] 使用selenium,xpath爬取京东手机
- JGUI源码:Tab组件实现(9)
- 程序导致IIS服务器应用程序池停止
- Spark基础脚本入门实践3:Pair RDD开发
- 深入学习webpack
- hadoop 遇到java.net.ConnectException: to 0.0.0.0:10020 failed on connection
- jetty安装、配置、优化
- flask写入数据库
- 机器学习入门-数值特征-进行多项式变化(将特征投影到高维度上) 1.PolynomialFeatures(将数据变化为多项式特征)
- P1402 酒店之王
- BZOJ1009: [HNOI2008]GT考试 矩阵快速幂+kmp+dp