最后一块石头的重量

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

每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为xy,且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/