last_stone_weight
1from heapq import heapify, heappop, heappush 2 3 4# @leet start 5class Solution: 6 def lastStoneWeight(self, stones: list[int]) -> int: 7 """ 8 This problem describes a game with a list of stones. 9 At every turn, we take the top 2 stones by weight and compare them. 10 If they have the same weight, they are removed. 11 Otherwise, the difference remains and is readded to the collection. 12 At the end of the game, there's either 0 or 1 stone left. 13 If there's no stones left, return 0. If there's 1, return its weight. 14 15 We approach this with a heap. We first multiply each stone weight by -1 16 to turn python's min-heap into a max heap. 17 Then, while there are two stones, we follow the rules: If they are the same weight, 18 remove them from the heap, otherwise, readd in the difference. 19 At the end, reverse the sign again to recover the correct weights and either 20 return 0 if the collection is empty or the last stone's weight. 21 """ 22 stones = list(map(lambda x: -x, stones)) 23 heapify(stones) 24 while len(stones) > 1: 25 top = heappop(stones) 26 next_top = heappop(stones) 27 if top != next_top: 28 diff = top - next_top 29 heappush(stones, diff) 30 31 if stones: 32 return -stones[0] 33 else: 34 return 0 35 36 37# @leet end 38sol = Solution() 39 40 41def test(): 42 assert sol.lastStoneWeight([2, 7, 4, 1, 8, 1]) == 1 43 assert sol.lastStoneWeight([1]) == 1
class
Solution:
6class Solution: 7 def lastStoneWeight(self, stones: list[int]) -> int: 8 """ 9 This problem describes a game with a list of stones. 10 At every turn, we take the top 2 stones by weight and compare them. 11 If they have the same weight, they are removed. 12 Otherwise, the difference remains and is readded to the collection. 13 At the end of the game, there's either 0 or 1 stone left. 14 If there's no stones left, return 0. If there's 1, return its weight. 15 16 We approach this with a heap. We first multiply each stone weight by -1 17 to turn python's min-heap into a max heap. 18 Then, while there are two stones, we follow the rules: If they are the same weight, 19 remove them from the heap, otherwise, readd in the difference. 20 At the end, reverse the sign again to recover the correct weights and either 21 return 0 if the collection is empty or the last stone's weight. 22 """ 23 stones = list(map(lambda x: -x, stones)) 24 heapify(stones) 25 while len(stones) > 1: 26 top = heappop(stones) 27 next_top = heappop(stones) 28 if top != next_top: 29 diff = top - next_top 30 heappush(stones, diff) 31 32 if stones: 33 return -stones[0] 34 else: 35 return 0
def
lastStoneWeight(self, stones: list[int]) -> int:
7 def lastStoneWeight(self, stones: list[int]) -> int: 8 """ 9 This problem describes a game with a list of stones. 10 At every turn, we take the top 2 stones by weight and compare them. 11 If they have the same weight, they are removed. 12 Otherwise, the difference remains and is readded to the collection. 13 At the end of the game, there's either 0 or 1 stone left. 14 If there's no stones left, return 0. If there's 1, return its weight. 15 16 We approach this with a heap. We first multiply each stone weight by -1 17 to turn python's min-heap into a max heap. 18 Then, while there are two stones, we follow the rules: If they are the same weight, 19 remove them from the heap, otherwise, readd in the difference. 20 At the end, reverse the sign again to recover the correct weights and either 21 return 0 if the collection is empty or the last stone's weight. 22 """ 23 stones = list(map(lambda x: -x, stones)) 24 heapify(stones) 25 while len(stones) > 1: 26 top = heappop(stones) 27 next_top = heappop(stones) 28 if top != next_top: 29 diff = top - next_top 30 heappush(stones, diff) 31 32 if stones: 33 return -stones[0] 34 else: 35 return 0
This problem describes a game with a list of stones. At every turn, we take the top 2 stones by weight and compare them. If they have the same weight, they are removed. Otherwise, the difference remains and is readded to the collection. At the end of the game, there's either 0 or 1 stone left. If there's no stones left, return 0. If there's 1, return its weight.
We approach this with a heap. We first multiply each stone weight by -1 to turn python's min-heap into a max heap. Then, while there are two stones, we follow the rules: If they are the same weight, remove them from the heap, otherwise, readd in the difference. At the end, reverse the sign again to recover the correct weights and either return 0 if the collection is empty or the last stone's weight.
sol =
<Solution object>
def
test():