您的位置: 首页  >  IT文章  >  最后一块石头的重量 最后一块石头的重量

最后一块石头的重量 最后一块石头的重量

分类: IT文章 • 2022-05-11 22:58:41

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

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

相关推荐