Go语言LeetCode题解1046最后一块石头的重量
作者:刘09k11 时间:2024-05-29 22:08:19
题目描述
1046. 最后一块石头的重量 - 力扣(LeetCode)
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x
和 y
,且 x <= y
。那么粉碎的可能结果如下:
如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。
示例:
输入:[2,7,4,1,8,1]
输出:1
解释:
先选出 7 和 8,得到 1,所以数组转换为 [2,4,1,1,1],
再选出 2 和 4,得到 2,所以数组转换为 [2,1,1,1],
接着是 2 和 1,得到 1,所以数组转换为 [1,1,1],
最后选出 1 和 1,得到 0,最终数组转换为 [1],这就是最后剩下那块石头的重量。
提示:
1 <= stones.length <= 30
1 <= stones[i] <= 1000
思路分析
这里用到了Arrays.sort排序,得到了从小到大的数组。
接下来用lastIndex指针指向未被粉碎的最后一个元素,取两个最大的石头,下标lastIndex,lastIndex-1。两者相减的差值赋给lastIndex-1,再移动下lastIndex指针就相当于删除了最后一个元素了
也可以改写成递归,思路是一样的。
AC 代码
import java.util.Arrays;
class Solution {
//一堆石头 每一颗石头重量都是整数
// 每一回合 选出两颗重量最大的石头 x、y x<=y
// x==y 完全粉碎 x!=y y=y-x
// 最后最多会剩下一颗石头 返回该石头重量 如果没有剩下 则返回0
private int lastIndex;
private int left;
public int lastStoneWeight(int[] stones) {
lastIndex = stones.length-1;
Arrays.sort(stones);
while (lastIndex>=1){
left = stones[lastIndex]-stones[lastIndex-1];
if (left==0){
lastIndex=lastIndex-2;
if (lastIndex==-1){
return 0;
}
}else {
stones[--lastIndex]=left;
Arrays.sort(stones);
}
}
return stones[lastIndex];
}
}
参考
非排序法 - 最后一块石头的重量 - 力扣(LeetCode)
来源:https://juejin.cn/post/7181772216777277496
标签:Go,LeetCode,石头重量
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
MySQL中表锁和行锁机制浅析(源码篇)
2024-01-27 22:12:55
![](https://img.aspxhome.com/file/2023/9/119719_0s.jpg)
JSP学生信息管理系统设计
2023-07-13 03:37:30
Python使用pickle进行序列化和反序列化的示例代码
2022-11-17 10:46:22
![](https://img.aspxhome.com/file/2023/5/72865_0s.png)
Mysql逗号拼接字符串的关联查询以及统计问题
2024-01-28 12:15:03
python基于queue和threading实现多线程下载实例
2023-02-04 09:58:22
javascript中if和switch,==和===详解
2024-04-22 13:23:28
![](https://img.aspxhome.com/file/2023/0/135730_0s.jpg)
django主动抛出403异常的方法详解
2023-03-28 17:40:10
![](https://img.aspxhome.com/file/2023/9/103479_0s.png)
php开启mysqli扩展之后如何连接数据库
2023-11-14 17:36:08
python起点网月票榜字体反爬案例
2021-03-11 02:56:05
![](https://img.aspxhome.com/file/2023/1/93441_0s.jpg)
Python生成pdf目录书签的实例方法
2023-10-11 15:43:21
![](https://img.aspxhome.com/file/2023/0/78780_0s.png)
Python定时器实例代码
2021-11-18 23:03:37
用python写扫雷游戏实例代码分享
2023-03-31 05:12:38
简单的网站页面有什么好处
2007-11-15 06:28:00
Python实现图像尺寸和格式转换处理的示例详解
2021-02-17 06:33:10
TypeScript入门-接口
2024-06-07 15:55:26
Python中的tuple元组详细介绍
2023-03-02 03:54:47
Python中方法的缺省参数问题解读
2022-10-07 17:00:45
![](https://img.aspxhome.com/file/2023/9/92059_0s.png)
FireScope-面向Web开发者和设计者的参考手册
2009-03-22 15:35:00
![](https://img.aspxhome.com/file/UploadPic/20093/22/01_b-44s.jpg)
js控制div弹出层实现方法
2023-10-15 05:53:28
c#连接mysql数据库的方法
2024-01-23 02:52:32