博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
力扣题解-1046. 最后一块石头的重量
阅读量:4299 次
发布时间:2019-05-27

本文共 961 字,大约阅读时间需要 3 分钟。

题目:1046. 最后一块石头的重量

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;

如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/last-stone-weight
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

利用优先级队列(堆头元素最大的最大堆),将全部石头放入队列;

每次从队列中取出两块石头,然后进行处理,直至最后队列不足两块石头为止。

代码

class Solution {
public: int lastStoneWeight(vector
& stones) {
priority_queue
, less
> que; for(auto stone: stones) {
que.push(stone); } while (que.size() > 1) {
int y = que.top(); que.pop(); int x = que.top(); que.pop(); if (x == y) {
; } else {
que.push(y-x); } } if (que.empty()) {
return 0; } return que.top(); }};
你可能感兴趣的文章
Python+Selenium基础篇之4-XPath的使用
查看>>
Python+Selenium基础篇之5-第一个完整的自动化测试脚本
查看>>
Python+Selenium练习篇之8-利用css定位元素
查看>>
Python+Selenium练习篇之19-断言页面标题
查看>>
Python+Selenium练习篇之20-获取元素上面的文字
查看>>
Python+Selenium练习篇之21-验证控件是否被选中
查看>>
Python+Selenium练习篇之22-获取页面元素大小
查看>>
Python+Selenium练习篇之23-组合键-全选文字
查看>>
Python+Selenium练习篇之24-组合键-退格键删除文字
查看>>
Python+Selenium练习篇之25-鼠标右键
查看>>
Python+Selenium练习篇之26-执行JavaScript
查看>>
Jenkins高级篇之Pipeline实践篇-5-Selenium和Jenkins持续集成-Pipelinejob草稿版
查看>>
Jenkins高级篇之Pipeline实践篇-6-Selenium和Jenkins持续集成-pipeline参数化构建selenium自动化测试
查看>>
Jenkins高级篇之Pipeline实践篇-7-Selenium和Jenkins持续集成-publish html report插件的pipeline使用介绍
查看>>
Jenkins高级篇之Pipeline实践篇-8-Selenium和Jenkins持续集成-添加事后删除报告功能和解决报告名称硬编码
查看>>
Jenkins高级篇之Pipeline实践篇-9-Selenium和Jenkins持续集成-日志文件归档和插件rebuild介绍--完结篇
查看>>
Java多线程-48-单例设计模式
查看>>
Java多线程-49-Runtime类学习
查看>>
Java多线程-50-Timer类
查看>>
Java多线程-51-两个线程之间的通信
查看>>