【Day 86 】2023-05-10 - 1046.最后一块石头的重量

[azl397985856]

1046.最后一块石头的重量

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/last-stone-weight/

前置知识

• 堆

  题目描述

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

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

[snmyj]

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        int n=stones.size();
        if(n==1) return stones[0];

        for(int i=0;i<n-1;i++){
            sort(stones.begin(),stones.end(),[&](int a,int b){return a>b;});
            stones[0]-=stones[1];
            stones[1]=0;
        }
        return stones[0];
    }
};

[NorthSeacoder]

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
    const heap = new MaxHeap();

    for (let stone of stones) {
        heap.push(stone);
    }
    // console.log(heap.heap)
    let stone1 = heap.pop();
    let stone2 = heap.pop();
    while (stone2) {
        const diff = Math.abs(stone1 - stone2);
        if (diff > 0) {
            heap.push(diff);
        }
        // console.log(stone1, stone2)
        stone1 = heap.pop();
        stone2 = heap.pop();
    }
    return stone1 || 0
};

class MaxHeap {
    constructor() {
        this.heap = [0];
    }
    //大->up
    shiftUp(i) {
        while (i >> 1 > 0) {
            let parentI = i >> 1;
            const parent = this.heap[parentI];
            const cur = this.heap[i];
            if (cur > parent) {
                [this.heap[parentI], this.heap[i]] = [cur, parent];
            }
            i = parentI
        }
    }
    getMaxChild(i) {
        const len = this.heap.length-1
        if (2 * i + 1 > len) return 2 * i;
        const left = this.heap[2 * i]
        const right = this.heap[2 * i + 1];
        if (left > right) return 2 * i;
        return 2 * i + 1
    }
    //小->下
    shiftDown(i) {
        const len = this.heap.length;
        //有子节点时
        while (2 * i < len) {
            const childI = this.getMaxChild(i);
            const child = this.heap[childI];
            const cur = this.heap[i];
            if (cur < child) {
                [this.heap[childI], this.heap[i]] = [cur, child]
            }
            i = childI;
        }
    }

    pop() {
        if (this.heap[0] === 0) return;
        const res = this.heap[1];
        this.heap[1] = this.heap[this.heap.length - 1];
        this.heap.pop();
        this.heap[0]--
        this.shiftDown(1);
        return res
    }

    getTop() {
        return this.heap[1]
    }

    push(val) {
        this.heap.push(val);
        this.heap[0]++
        this.shiftUp(this.heap.length - 1);
    }

}

[lp1506947671]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        h = [-stone for stone in stones]
        heapq.heapify(h)

        while len(h) > 1:
            a, b = heapq.heappop(h), heapq.heappop(h)
            if a != b:
                heapq.heappush(h, a - b)
        return -h[0] if h else 0

复杂度分析

令石头个数为 NN

• 时间复杂度：O(NlogN)

• 空间复杂度：O(N)

[LIMBO42]

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> que(stones.begin(), stones.end());
        while(que.size() > 1) {
            int x = que.top();
            que.pop();
            int y = que.top();
            que.pop();
            int diff = abs(x - y);
            if(diff == 0) continue;
            que.push(x-y);
        }
        if(que.size() == 1) return que.top();
        return 0;
    }
};

[bookyue]

    public int lastStoneWeight(int[] stones) {
        var pq = new PriorityQueue<Integer>(Comparator.reverseOrder());

        for (int stone : stones) pq.add(stone);

        while (pq.size() > 1) {
            int y = pq.poll();
            int x = pq.poll();

            if (y > x) pq.offer(y - x);
        }

        return pq.isEmpty() ? 0 : pq.poll();
    }

[Diana21170648]

思路

先入堆，然后出堆，粉碎之后，再入堆或者取两个数，直到堆的长度不足两个，返回堆的元素，注意是大顶堆

import heapq
from typing import List
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        h=[-stone for stone in stones]
        heapq.heapify(h)
        n=len(h)
        while n>1:
            a = heapq.heappop(h) 
            b = heapq.heappop(h)
            if a !=b:
                heapq.heappush(h,a-b)
        return -h[0] if h else 0

**复杂度分析**
- 时间复杂度：O(NlogN)，其中 N 为数组长度，排序。
- 空间复杂度：O(N),堆的大小

[huizsh]

class Solution {

public int lastStoneWeight(int[] stones) {

    PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);

    for (int i : stones)
        pq.offer(i);

    while (pq.size() >= 2) {

        int x = pq.poll();
        int y = pq.poll();

        if (x > y)
            pq.offer(x - y);
    }

    return pq.size() == 1 ? pq.peek() : 0;
}

}

[wangqianqian202301]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        for i, s in enumerate(stones):
            stones[i] = -s
        heapify(stones)  
        while stones:
            s1 = -heappop(stones)  
            if not stones:  
                return s1
            s2 = -heappop(stones)  
            if s1 > s2:
                heappush(stones, s2-s1)  
        return 0  

[kofzhang]

思路

堆实现

复杂度

时间复杂度：O(nlogn) 空间复杂度：O(n)

代码

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        heap = []
        for i in stones:
            heapq.heappush(heap,-i)
        while len(heap)>1:
            t1 = -heapq.heappop(heap)
            t2 = -heapq.heappop(heap)
            heapq.heappush(heap,-abs(t1-t2))
        return -heap[0]

[zhangyu1131]

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        // 堆
        while (stones.size() > 1)
        {
            make_heap(stones.begin(), stones.end());
            int largest = stones[0];
            pop_heap(stones.begin(), stones.end());
            stones.pop_back();
            int second_largest = stones[0];
            pop_heap(stones.begin(), stones.end());
            stones.pop_back();
            int left = largest - second_largest;
            if (left > 0)
            {
                stones.push_back(left);
            }
        }

        return stones.empty() ? 0 : stones[0];
    }
};

[tzuikuo]

思路

递归

代码

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        if(stones.size()==1) return stones[0];
        else if(stones.size()==0) return 0;
        else{
            sort(stones.begin(),stones.end());
            int n=stones.size();
            if(n>=2){
              if(stones[n-1]==stones[n-2]){
                  stones.pop_back();
                  stones.pop_back();
              }
              else{
                  int temp=stones[n-1]-stones[n-2];
                  stones.pop_back();
                  stones.pop_back();
                  stones.push_back(temp);
              }  
            }
            return lastStoneWeight(stones);
        }
    }
};

复杂度分析 -待定

[harperz24]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        if len(stones) == 1:
            return stones[0]

        maxheap = [-s for s in stones]
        heapq.heapify(maxheap)

        while len(maxheap) >= 2:
            y = -heapq.heappop(maxheap)
            x = -heapq.heappop(maxheap)
            if x != y:
                heapq.heappush(maxheap, -(y - x))

        return -maxheap[0] if maxheap else 0

[RestlessBreeze]

code

class Solution {
public:
    priority_queue<int> q;
    int lastStoneWeight(vector<int>& stones) {
        for (int i = 0; i < stones.size(); i++)
            q.push(stones[i]);
        while (q.size() > 1)
        {
            int x = q.top();
            q.pop();
            int y = q.top();
            q.pop();
            int m = x - y;
            if (m != 0) q.push(m);
        }
        return q.size() == 0 ? 0 : q.top();
    }
};

[Lydia61]

1046. 最后一块石头的重量

思路

最大堆排序

代码

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # 初始化
        heap = [-stone for stone in stones]
        heapq.heapify(heap)

        # 模拟
        while len(heap) > 1:
            x,y = heapq.heappop(heap),heapq.heappop(heap)
            if x != y:
                heapq.heappush(heap,x-y)

        if heap: return -heap[0]
        return 0

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[X1AOX1A]

class Solution: def lastStoneWeight(self, stones: List[int]) -> int: h = [-stone for stone in stones] heapq.heapify(h)

    while len(h) > 1:
        a, b = heapq.heappop(h), heapq.heappop(h)
        if a != b:
            heapq.heappush(h, a - b)
    return -h[0] if h else 0

[sye9286]

代码

var lastStoneWeight = function(stones) {
    const pq = new MaxPriorityQueue();
    for (const stone of stones) {
        pq.enqueue('x', stone);
    }

    while (pq.size() > 1) {
        const a = pq.dequeue()['priority'];
        const b = pq.dequeue()['priority'];
        if (a > b) {
            pq.enqueue('x', a - b);
        }
    }
    return pq.isEmpty() ? 0 : pq.dequeue()['priority'];
};

复杂度分析

• 时间复杂度：O(N log N)
• 空间复杂度：O(N)

[Fuku-L]

代码

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){
            int a = pq.poll();
            int b = pq.poll();
            if(a>b){
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

复杂度分析

• 时间复杂度：O(NlogN)，其中 N 为数组长度。
• 空间复杂度：O(N)

[enrilwang]

class Solution { public: int lastStoneWeight(vector& stones) { int n=stones.size(); if(n==1) return stones[0];

    for(int i=0;i<n-1;i++){
        sort(stones.begin(),stones.end(),[&](int a,int b){return a>b;});
        stones[0]-=stones[1];
        stones[1]=0;
    }
    return stones[0];
}

};

[kangliqi1]

class Solution {

public int lastStoneWeight(int[] stones) {

    PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);

    for (int i : stones)
        pq.offer(i);

    while (pq.size() >= 2) {

        int x = pq.poll();
        int y = pq.poll();

        if (x > y)
            pq.offer(x - y);
    }

    return pq.size() == 1 ? pq.peek() : 0;
}

}

[FireHaoSky]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # 初始化
        heap = [-stone for stone in stones]
        heapq.heapify(heap)

        # 模拟
        while len(heap) > 1:
            x,y = heapq.heappop(heap),heapq.heappop(heap)
            if x != y:
                heapq.heappush(heap,x-y)

        if heap: return -heap[0]
        return 0

[JasonQiu]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = [s * -1 for s in stones]
        heapq.heapify(stones)
        while len(stones) >= 2:
            x = heapq.heappop(stones)
            if stones:
                y = heapq.heappop(stones)
                if x != y:
                    heapq.heappush(stones, -abs(x - y))
        return 0 if not stones else -stones[0]

[Jetery]

class Solution {
    public int lastStoneWeight(int[] stones) {

        PriorityQueue<Integer> heap = new PriorityQueue<>(stones.length, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for(int num : stones) {
            heap.offer(num);
        }

        while (heap.size() > 1) {
            int largest = heap.poll();
            int large = heap.poll();
            if (largest > large) {
                heap.offer(largest - large);
            }
        }
        return heap.isEmpty() ? 0 : heap.poll();
    }
}

[joemonkeylee]

function lastStoneWeight(stones: number[]): number {
    stones.sort((a,b)=>{return a-b});
    while(stones.length >= 2){
        let len:number = stones.length;
        let n1:number = stones[len-2];
        let n2:number = stones[len-1];
        stones = stones.slice(0,len-2);
        let k = Math.abs(n1-n2);
        if(k){
            if(!stones.length){
                stones.push(k);
                break;
            }
            for(let i=0;i<stones.length; i++){
                if(stones[i]>k){
                    stones.splice(i,0,k);
                    break;
                }
                if(i === stones.length-1){
                    stones.push(k);
                    break;
                }
            }
        }
    }
    return stones.length?stones[0]:0;
};