1046. 最后一块石头的重量

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

每一回合,从中选出两块最重的石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/last-stone-weight
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

对数组从打到小排序,每次将前两个的和加如数组对应位置并删除前两个

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {
    stones.sort((a, b) => b - a)
    while (stones.length>1) {
        let a=stones[0]-stones[1]
        stones.splice(0,2)
        if(a!=0){
            let l=stones.length
            for(let i=0;i<stones.length;i++){
                if(stones[i]<=a){
                    stones.splice(i,0,a)
                    break
                }
            }
            if(stones.length==l){
                stones.push(a)
            }
        }
    }
    return stones[0]?stones[0]:0
};

发表评论

您的电子邮箱地址不会被公开。