【Day 86 】2022-06-25 - 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

[djd28176]

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());

        for(int stone:stones){
            heap.add(stone);
        }

        while(heap.size()>1){
            int stone1 = heap.remove();
            int stone2 = heap.remove();

            if(stone1 != stone2){
                heap.add(stone1-stone2);
            }
        }

        return heap.isEmpty()? 0: heap.remove();
    }
}

[fhuang5]

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;
    }
}

[MichaelXi3]

Idea

Max Heap

Code

class Solution {
    public int lastStoneWeight(int[] stones) {
        Comparator<Integer> c = new compareByWeight();
        PriorityQueue<Integer> heap = new PriorityQueue<>(c);

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

        while (heap.size() >= 2) {
            int a = heap.poll();
            int b = heap.poll();
            heap.offer(Math.abs(a - b));
        }

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

    public class compareByWeight implements Comparator<Integer> {
        public int compare (Integer a, Integer b) {
            return b - a;
        }
    }
}

[asuka1h]

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> q;
        for(auto i : stones){
            q.push(i);
        }
        while(q.size() > 1){
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            if(abs(a-b) != 0){
                q.push(abs(a-b));
            }
        }
        return q.empty()? 0 : q.top();
    }
};

[JiangWenqi]

class Solution {
 public:
  int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> q;
    for (int& stone : stones) {
      q.push(stone);
    }
    while (q.size() > 1) {
      int big = q.top();
      q.pop();
      int small = q.top();
      q.pop();
      if (big == small)
        q.push(0);
      else if (big != small)
        q.push(big - small);
    }
    return q.top();
  }
};

[houmk1212]

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int stone : stones) {
            heap.offer(stone);
        }
        while (heap.size() > 1) {
            int a = heap.poll();
            int b = heap.poll();
            if (a > b) {
                heap.offer(a - b);
            } else if (a < b) {
                heap.offer(b - a);
            }
        }
        return heap.isEmpty() ? 0 : heap.peek();
    }
}

[miss1]

思路

堆，优先队列。每次取队列的末尾两个数，相减后重新入队（两个值相等时不入队）

实现

var lastStoneWeight = function(stones) {
  let p = new priorityQueue();
  for (let s of stones) p.enqueue(s);
  while (p.size() > 1) {
    let y = p.dequeue();
    let x = p.dequeue();
    if (x !== y) p.enqueue(y - x);
  }
  return p.size() === 0 ? 0 : p.dequeue();
};

class priorityQueue {
  constructor() {
    this.heap = [];
  }
  search(target) {
    let low = 0, high = this.size();
    while (low < high) {
      let mid = low + ((high - low) >> 1);
      if (this.heap[mid] > target) high = mid;
      else low = mid + 1;
    }
    return low;
  }
  enqueue(val) {
    let index = this.search(val);
    this.heap.splice(index, 0, val);
  }
  dequeue() {
    return this.heap.pop();
  }
  size() {
    return this.heap.length;
  }
}

复杂度

• time: O(n²)
• space: O(n)

[ShawYuan97]

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        """
        动态求求极值 
        """
        heap = [-x for x in stones]
        heapq.heapify(heap)
        while len(heap)>1:
            x = heapq.heappop(heap)
            y = heapq.heappop(heap)
            z = x-y if x > y else y-x
            if z != 0 :
                heapq.heappush(heap,-z)
        return 0 if not heap else -heap[0]

复杂度分析

令 n 为数组长度。

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

[currybeefer]

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;
}

}

[EldinZhou]

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool  { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
func (h *hp) push(v int)         { heap.Push(h, v) }
func (h *hp) pop() int           { return heap.Pop(h).(int) }

func lastStoneWeight(stones []int) int {
    q := &hp{stones}
    heap.Init(q)
    for q.Len() > 1 {
        x, y := q.pop(), q.pop()
        if x > y {
            q.push(x - y)
        }
    }
    if q.Len() > 0 {
        return q.IntSlice[0]
    }
    return 0
}

[wychmod]

思路

大根堆

代码

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

[ghost]

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

        while(len(stones)>1):
            x = heapq.heappop(stones)
            y = heapq.heappop(stones)
            heapq.heappush(stones, x-y)

        return -stones[0]

[maggiexie00]

def lastStoneWeight(self, stones: List[int]) -> int:
    heap,ans=[],0
    for i in range(len(stones)):
        heapq.heappush(heap,-stones[i])

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

    if heap:
        ans=-heapq.heappop(heap)

    return ans

[xil324]

class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        res = 0; 
        heap = []; 
        for stone in stones:
            heapq.heappush(heap,stone * (-1));
        while len(heap) > 1:
            print(heap)
            y = heapq.heappop(heap) * (-1); 
            x = heapq.heappop(heap) * (-1);
            if x != y:
                heapq.heappush(heap, (y-x) * (-1)); 
        return 0 if len(heap) == 0 else -heap[0]

[Ellie-Wu05]

思路一：array-based simulation

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:

        def remove_largest():
            index_of_max = stones.index(max(stones))

            # swap
            stones[-1],stones[index_of_max] = stones[index_of_max],stones[-1]

            return stones.pop()

        while len(stones)>1:
            s1 = remove_largest()
            s2 = remove_largest()

            if s1 != s2:
                stones.append(s1-s2)

        return stones[0] if stones else 0

复杂度

时间：On^2 空间：On 或者O1

思路二： Sorted Array-Based Simulation

代码

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:

        stones.sort()

        while len(stones) >1:
            s1 = stones.pop()
            s2 = stones.pop()

            if s1!= s2:
                stones.append(s1-s2)
            stones.sort()

        return stones[0] if stones else 0

复杂度

时间：On^2 空间：On 或者O1

思路三：Heap-Based Simulation

在python中，heapq是min heap 所以我们要乘以-1 来找最大的

代码

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:

        for i in range(len(stones)):
            stones[i] *=-1

        heapq.heapify(stones)

        while len(stones)>1:
            s1 = heapq.heappop(stones)
            s2 = heapq.heappop(stones)

            if s1 != s2:
                heapq.heappush(stones,s1-s2)

        return -heapq.heappop(stones) if stones else 0

复杂度

时间：Onlogn 空间：On 或者Ologn

[freedom0123]

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((x,y) -> y - x);
        for(int i = 0; i < stones.length; i++) pq.add(stones[i]);
        while(pq.size() >= 2) {
            int x = pq.poll();
            int y = pq.poll();
            if(x > y) pq.add(x - y);
        }
        return pq.size() == 1 ? pq.peek() : 0;
    }
}

[Geek-LX]

6.25

思路：堆

代码：

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

复杂度分析

时间复杂度：O(NlogN)

空间复杂度：O(N)

[LQyt2012]

思路

大顶堆，python可以将list中的元素去相反数。然后用直接调用heapq。

代码

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        negative_stones = [-i for i in stones]
        heapq.heapify(negative_stones)
        while len(negative_stones) > 0:
            if len(negative_stones) == 1:
                return -heapq.heappop(negative_stones)
            else:
                x = -heapq.heappop(negative_stones)
                y = -heapq.heappop(negative_stones)
                if x == y:
                    continue
                else:
                    heapq.heappush(negative_stones, y-x)
        return 0

import "container/heap"

type heapInt []int

func (h heapInt) Len() int {
    return len(h)
}

func (h heapInt) Less(i, j int) bool {
    return h[i] > h[j]
}

func (h heapInt) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *heapInt) Push(v interface{}) {
    *h = append(*h, v.(int))
}

func (h *heapInt) Pop() interface{} {
    old := *h
    n := h.Len()
    v := old[n-1]
    *h = old[:n-1]
    return v
}

func lastStoneWeight(stones []int) int {
    h := &heapInt{}    
    *h = append(*h, stones...)
    heap.Init(h)
    for h.Len() > 0 {
        if h.Len() == 1 {
            return int(heap.Pop(h).(int))
        } else {
            x := int(heap.Pop(h).(int))
            y := int(heap.Pop(h).(int))
            if x == y {
                continue
            } else {
                heap.Push(h, x-y)
            }
        }
    }
    return 0
}

复杂度分析

时间复杂度：O(NlogN)
空间复杂度：O(N)

[XXjo]

var lastStoneWeight = function(stones) {
    let mpq = new MaxPriorityQueue();
    for(let stone of stones){
        mpq.enqueue("x", stone);
    }

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

[taojin1992]

// time: O(nlogn), n = stones.length
// space: O(n)

class Solution {
    public int lastStoneWeight(int[] stones) {
        if (stones.length == 1) return stones[0];
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));
        for (int stone : stones) {
            maxHeap.offer(stone);
        }
        while (maxHeap.size() > 1) {
            int max = maxHeap.poll();
            int submax = maxHeap.poll();
            if (max != submax) {
                maxHeap.offer(max - submax);
            }
        }
        return maxHeap.size() == 0 ? 0 : maxHeap.poll();
    }
}

[sallyrubyjade]

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {
    let size = stones.length
    if(size <2){
        return stones[0] || 0
    }
    stones = stones.sort((a,b)=>a - b);
    while(stones.length > 1){       
        let max = stones.pop();
        let max2 = stones.pop();
        if(max !== max2){
            stones.splice(binarySearch(stones,max - max2),0,max - max2)
        }
    }
    return stones[0] || 0
};

function binarySearch(array,target){
    let size = array.length;
    if(size === 0){
        return 0
    }
    let high = size - 1;
    let low = 0;
    let mid = 0;
    if(target <= array[low]){
        return low
    }
    if(target > array[high]){
        return size
    }
    while(true){
        mid = Math.floor((high + low)/2);
        if(array[mid] > target){
            high = mid
        } else if(array[mid] < target){
            low = mid
        } else {
            return mid
        }
        if(array[low] < target && array[low+1] >= target){
            return low + 1
        }
    }
}

[xiayuhui231]

class Solution { public int lastStoneWeight(int[] stones) { if (stones.length == 1) return stones[0]; PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> (b - a)); for (int stone : stones) { maxHeap.offer(stone); } while (maxHeap.size() > 1) { int max = maxHeap.poll(); int submax = maxHeap.poll(); if (max != submax) { maxHeap.offer(max - submax); } } return maxHeap.size() == 0 ? 0 : maxHeap.poll(); } }

[flyzenr]

class Heap:
    def __init__(self,desc=False):
        """
        初始化，默认创建一个小顶堆
        """
        self.heap = []
        self.desc = desc

    @property
    def size(self):
        return len(self.heap)

    def top(self):
        if self.size:
            return self.heap[0]
        return None

    def push(self,item):
        """
        添加元素
        第一步，把元素加入到数组末尾
        第二步，把末尾元素向上调整
        """
        self.heap.append(item)
        self._sift_up(self.size-1)

    def pop(self):
        """
        弹出堆顶
        第一步，记录堆顶元素的值
        第二步，交换堆顶元素与末尾元素
        第三步，删除数组末尾元素
        第四步，新的堆顶元素向下调整
        第五步，返回答案
        """
        item = self.heap[0]
        self._swap(0,self.size-1)
        self.heap.pop()
        self._sift_down(0)
        return item

    def _smaller(self,lhs,rhs):
        return lhs > rhs if self.desc else lhs < rhs

    def _sift_up(self,index):
        """
        向上调整
        如果父节点和当前节点满足交换的关系
        （对于小顶堆是父节点元素更大，对于大顶堆是父节点更小），
        则持续将当前节点向上调整
        """
        while index:
            parent = (index-1) // 2

            if self._smaller(self.heap[parent],self.heap[index]):
                break

            self._swap(parent,index)
            index = parent

    def _sift_down(self,index):
        """
        向下调整
        如果子节点和当前节点满足交换的关系
        （对于小顶堆是子节点元素更小，对于大顶堆是子节点更大），
        则持续将当前节点向下调整
        """
        # 若存在子节点
        while index*2+1 < self.size:
            smallest = index
            left = index*2+1
            right = index*2+2

            if self._smaller(self.heap[left],self.heap[smallest]):
                smallest = left

            if right < self.size and self._smaller(self.heap[right],self.heap[smallest]):
                smallest = right

            if smallest == index:
                break

            self._swap(index,smallest)
            index = smallest

    def _swap(self,i,j):
        self.heap[i],self.heap[j] = self.heap[j],self.heap[i]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # 初始化大顶堆
        heap = Heap(desc=True)
        for stone in stones:
            heap.push(stone)

        # 模拟
        while heap.size > 1:
            x,y = heap.pop(),heap.pop()
            if x != y:
                heap.push(x-y)
        if heap.size: return heap.heap[0]
        return 0

[Yongxi-Zhou]

思路

Heap simulation

代码

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

            # print(pq)
            while len(pq) > 1:

                first = heapq.heappop(pq) * -1
                second = heapq.heappop(pq) * -1
                # print(first, second, pq)
                heapq.heappush(pq, -abs(first - second))
            res =  heapq.heappop(pq)
            return res if res >= 0 else -res

复杂度

time O(nlogn) space O(n)