最后一块石头的重量
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为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],这就是最后剩下那块石头的重量。
题解
/**
* @param {number[]} stones
* @return {number}
*/
var lastStoneWeight = function(stones) {
const findMax = function(arr){
let index = 0;
let max = ~~arr[0];
arr.forEach((v,i) => {
if(v > max) {
index = i;
max = v;
}
})
return [index, max];
}
if(stones.length === 0) return 0;
if(stones.length === 1) return stones[0];
while(stones.length > 1) {
let [yIndex, y] = findMax(stones);
stones.splice(yIndex, 1);
let [xIndex, x] = findMax(stones);
stones.splice(xIndex, 1);
if (x !== y) stones.push(y-x);
}
return stones.length === 1 ? stones[0] : 0;
};
思路
完全按照题目要求模拟即可,每次都取出最重的两块石头,之后判断这两块石头的重量,如果不相同再将其差值置入数组,题目使用优先队列做也可以,在题解中是自行实现了取得最大值极其索引的函数,如果直接使用Math.max()
无法取得索引,而之后需要使用索引来移除该值,所以需要自行实现取得索引及最大值的方法。首先定义函数以寻找最大值和索引,将最大值索引定义为0
,将最大值定义为数组第一个,如果数组是空数组则此处会将undefined
转为0
,之后遍历数组,如果数组中的值大于定义的max
值,则将其索引与值记录,最终返回索引与最大值。之后判断数组长度,如果数组长度为0
则直接返回0
,如果长度为1
则返回这个值。之后定义循环,循环条件为数组长度在两个及以上,之后取得当前最大值及其索引,将该值弹出数组,再取得当前最大值及其索引,将该值弹出数组,之后如果两个最大值不相同,则将差值置入数组,最后判断数组长度如果是1
则返回其中的值,否则就返回0
。
每日一题
https://github.com/WindrunnerMax/EveryDay
参考
https://leetcode-cn.com/problems/last-stone-weight/