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 weightxis destroyed, and the stone of weightyhas a new weighty - 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 <= 301 <= 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