攻城獅
Not a programmer 不工程的攻城獅

Follow

Not a programmer 不工程的攻城獅

Follow

LeetCode Solution, Easy, 1046. Last Stone Weight

最後石頭重量

攻城獅's photo
攻城獅
·Apr 7, 2022·
Play this article

1046. Last Stone Weight

題目敘述

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 a new weight y - x.

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

Return the smallest possible weight of the left 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

Hint 1:

Simulate the process. We can do it with a heap, or by sorting some list of stones every time we take a turn.

題目翻譯

給定一個整數陣列 stones,每個元素紀錄的是每個石頭的重量。現在我們會找出兩個最重的石頭互相撞擊,如果兩個重量相同就會兩個都消失;如果一大一小則小的會消失,大的會變成剩下 x-y 的重量。這題就是要一直互相撞擊,留下最後一個石頭。要找出其重量

解法解析

這題可以用 Sorted array 或是用 Max Heap,看到最多人使用這兩種方式。因為其寫法簡單且直覺,但是其時間複雜度相對的高,因為是每次比對完之後都要重新做一次排序。

Sorted array

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones.sort()
        while len(stones) > 1:
            stone_1 = stones.pop()
            stone_2 = stones.pop()
            if stone_1 != stone_2:
                bisect.insort(stones, stone_1 - stone_2)
        return stones[0] if stones else 0

Heap

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

        # Make all the stones negative. We want to do this *in place*, to keep the
        # space complexity of this algorithm at O(1). :-)
        for i in range(len(stones)):
            stones[i] *= -1

        # Heapify all the stones.
        heapq.heapify(stones)

        # While there is more than one stone left, remove the two
        # largest, smash them together, and insert the result
        # back into the heap if it is non-zero.
        while len(stones) > 1:
            stone_1 = heapq.heappop(stones)
            stone_2 = heapq.heappop(stones)
            if stone_1 != stone_2:
                heapq.heappush(stones, stone_1 - stone_2)

        # Check if there is a stone left to return. Convert it back
        # to positive.
        return -heapq.heappop(stones) if stones else 0

我最後範例的解法則是使用了 Bucket sort,雖然第一眼沒有那麼好懂,但是時間複雜度是最低的。解法的概念是,將各個值放到各字對映的陣列索引上,然後紀錄該值有幾個 [2, 7, 4, 1, 8, 1] => [0, 2, 1, 0, 1, 0, 0, 1, 1]。然後從尾巴最大值開始向開頭比對。

解法範例

Go

func lastStoneWeight(stones []int) int {
    maxWeight := max(stones)
    buckets := make([]int, maxWeight+1)

    for _, value := range stones {
        buckets[value]++
    }

    biggestWeight := 0
    currentWeight := maxWeight
    for currentWeight > 0 {
        if buckets[currentWeight] == 0 {
            currentWeight--
        } else if biggestWeight == 0 {
            buckets[currentWeight] %= 2
            if buckets[currentWeight] == 1 {
                biggestWeight = currentWeight
            }
            currentWeight--
        } else {
            buckets[currentWeight]--
            if biggestWeight-currentWeight <= currentWeight {
                buckets[biggestWeight-currentWeight]++
                biggestWeight = 0
            } else {
                biggestWeight -= currentWeight
            }
        }
    }

    return biggestWeight
}

func max(stones []int) (max int) {
    max_one := stones[0]
    for _, value := range stones {
        if value > max_one {
            max_one = value
        }
    }
    return max_one
}

JavaScript

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
    const maxWeight = Math.max(...stones);
    const buckets = new Array(maxWeight + 1).fill(0);
    for (const weight of stones) {
        buckets[weight]++;
    }

    let biggestWeight = 0,
        currentWeight = maxWeight;
    while (currentWeight > 0) {
        if (buckets[currentWeight] === 0) {
            currentWeight--;
        } else if (biggestWeight === 0) {
            buckets[currentWeight] %= 2;
            if (buckets[currentWeight] === 1) {
                biggestWeight = currentWeight;
            }
            currentWeight--;
        } else {
            buckets[currentWeight]--;
            if (biggestWeight - currentWeight <= currentWeight) {
                buckets[biggestWeight - currentWeight]++;
                biggestWeight = 0;
            } else {
                biggestWeight -= currentWeight;
            }
        }
    }
    return biggestWeight;
};

Kotlin


PHP

class Solution
{

    /**
     * @param Integer[] $stones
     * @return Integer
     */
    function lastStoneWeight($stones)
    {
        $maxWeight = max($stones);
        $buckets = array_fill(0, $maxWeight + 1, 0);
        foreach ($stones as $stone) {
            $buckets[$stone]++;
        }

        $biggestWeight = 0;
        $currentWeight = $maxWeight;
        while ($currentWeight > 0) {
            if ($buckets[$currentWeight] == 0) {
                $currentWeight--;
            } else if ($biggestWeight == 0) {
                $buckets[$currentWeight] %= 2;
                if ($buckets[$currentWeight] == 1) {
                    $biggestWeight = $currentWeight;
                }
                $currentWeight--;
            } else {
                $buckets[$currentWeight]--;
                if ($biggestWeight - $currentWeight <= $currentWeight) {
                    $buckets[$biggestWeight - $currentWeight]++;
                    $biggestWeight = 0;
                } else {
                    $biggestWeight -= $currentWeight;
                }
            }
        }
        return $biggestWeight;
    }
}

Python

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

        # Set up the bucket array.
        max_weight = max(stones)
        buckets = [0] * (max_weight + 1)

        # Bucket sort.
        for weight in stones:
            buckets[weight] += 1

        # Scan through the weights.
        biggest_weight = 0
        current_weight = max_weight
        while current_weight > 0:
            if buckets[current_weight] == 0:
                current_weight -= 1
            elif biggest_weight == 0:
                buckets[current_weight] %= 2
                if buckets[current_weight] == 1:
                    biggest_weight = current_weight
                current_weight -= 1
            else:
                buckets[current_weight] -= 1
                if biggest_weight - current_weight <= current_weight:
                    buckets[biggest_weight - current_weight] += 1
                    biggest_weight = 0
                else:
                    biggest_weight -= current_weight
        return biggest_weight

Rust


Swift


Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this