LeetCode中最后一块石头的重量题解-java
题目
1046. 最后一块石头的重量
难度简单113收藏分享切换为英文接收动态反馈
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 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
题解
方法一:排序求差值
思路
将数组进行排序升序,从最后开始遍历,计算相邻差值赋值给后一位,将0赋值给前一位,然后再排序,依次遍历,到最后计算数组中最后一个值即为最后一块石头的重量的大小
代码实现
class Solution {
public int lastStoneWeight(int[] stones) {
// 对数组进行升序排序
Arrays.sort(stones);
int index = stones.length - 1;
// 从后遍历相邻元素差值,赋值给对应数组下标,并将前一个值赋值为0,排序,依次进行
for(int i = index; i > 0; i--){
stones[index] = stones[index] - stones[index-1];
stones[index - 1] = 0;
Arrays.sort(stones);
}
// 数组最后一个元素即为最后一块石头的重量
return stones[stones.length - 1];
}
}
复杂度分析
提交详情
方法二:最大堆
思路
将所有石头的重量放入最大堆中,每次依次从队列中取出最重的两块石头a,b ,必有a>=b,如果a>b,则将新石头a-b的差值放入最大堆中,如果a=b,则不会产生新石头,重复此过程,直到最大堆中的元素少于2块。
若最终剩下一块石头,则该石头即为最后一块石头的重量,返回该元素,若无石头剩下,最大堆为空,则返回0
代码实现
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) {
// 取出两个元素a,b
int a = pq.poll();
int b = pq.poll();
// 比较如a大于b,将其差值放入最大堆中
if (a > b) {
pq.offer(a - b);
}
}
// 如果最后最大堆为空,则最后一块石头重量为0.否则为最大堆中剩余的值
return pq.isEmpty() ? 0 : pq.poll();
}
}
复杂度分析
- 时间复杂度:O(nlogn),其中 n 是石头数量。每次从队列中取出元素需要花费 O(logn) 的时间,最多共需要粉碎 n−1 次石头。
- 空间复杂度:O(n)
提交详情
方法三:
思路
使用递归解决问题,最后条件:如果数组长度为2,则值为两个元素之间的差值;如果长度为1,则值为此元素,对数组进行排序,如果之后最后两个元素不为0,则值为 最后两个元素的差值,每次令数组最后一个元素为相邻两个元素的差值,倒数第二个元素的值为0,依次递归下去,直到长度为2或者为1,
代码实现
class Solution {
public int lastStoneWeight(int[] stones) {
// 如果长度为2,则值为两个元素的差值
if (stones.length == 2) {
return Math.abs(stones[0] - stones[1]);
}
// 如果长度为1,则为此元素
if (stones.length == 1) {
return stones[0];
}
// 进行升序排序
Arrays.sort(stones);
// 如果只有最后两个元素不为0 ,则值为最后两个元素得差值
if (stones[stones.length - 3] == 0) {
return stones[stones.length - 1] - stones[stones.length - 2];
}
// 最后一个元素的值为,最后一个元素的值与倒数第二个元素的差值
stones[stones.length - 1] = stones[stones.length - 1] - stones[stones.length - 2];
// 令倒数第二个元素的值为0
stones[stones.length - 2] = 0;
// 递归这个函数
return lastStoneWeight(stones);
}
}