1046.Last Stone Weight

tags: `Easy`,`Array`,`Heap`

題目描述

You are given an array of integers stones where stones[i] is the weight of the i^th stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

範例

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]
Output: 1

Constraints:

1 <= stones.length <= 30
1 <= stones[i] <= 1000

解答

Python

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

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

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

Ron ChenMon, Apr 24, 2023









































class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        self.heap = []
        def swap(i, j):
            tmp = self.heap[i]
            self.heap[i] = self.heap[j]
            self.heap[j] = tmp
        def insert(value):
            self.heap.append(value)
            k = len(self.heap) - 1
            while k > 0 and self.heap[k] > self.heap[(k-1)//2]:
                swap(k, (k-1)//2)
                k = (k-1)//2
        def pop():
            value = self.heap[0]
            self.heap[0] = self.heap[-1]
            self.heap.pop()
            k = 0
            while k * 2 + 1 < len(self.heap):
                j = k * 2 + 1
                if k * 2 + 2 < len(self.heap) and self.heap[k*2+2] > self.heap[k*2+1]:
                    j = k * 2 + 2
                if self.heap[j] > self.heap[k]:
                    swap(j, k)
                k = j
            return value

        for s in stones:
            insert(s)

        while len(self.heap) > 1:
            s1 = pop()
            s2 = pop()
            ret = abs(s1-s2)
            if ret > 0:
                insert(ret)
        if len(self.heap) > 0:
            return self.heap[0]
        else:
            return 0

gpwork4uMon, Apr 24, 2023

Javascript














function lastStoneWeight(stones) {
  const heap = new MaxHeap();
  for (const stone of stones) {
    heap.push(stone);
  }

  while (heap.queue.length > 1) {
    const max = heap.pop();
    const second = heap.pop();
    if (max !== second) heap.push(max - second);
  }

  return heap.queue.length === 0 ? 0 : heap.pop();
}

寫這題才發現我上次寫的maxheap有bug…趕緊改一下
用JS刷題貌似真的不太適合
MarsgoatMon, Apr 24, 2023

TypeScript















function lastStoneWeight(stones: number[]): number {
  if (stones.length === 0) return 0;
  if (stones.length === 1) return stones[0];

  const sortedList: number[] = [...stones].sort((a, b) => b - a);
  const smashedResult = sortedList[0] - sortedList[1];

  if (smashedResult > 0) {
    sortedList.splice(0, 2, smashedResult);
  } else {
    sortedList.splice(0, 2);
  }

  return lastStoneWeight(sortedList);
}

不會 heap 直接爆破
SheepMon, Apr 24, 2023

Reference

回到題目列表