【LeetCode】1046. Last Stone Weight 解答・解説【Python】

はじめに
1. ポイント
2. この記事で得られること
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, iterative
  2. 解答2:Python, ヒープキュー(優先度付きキュー)
終わりに
1. 補足・参考・感想
2. 疑問が解決した方は他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- ヒープキュー(優先度付きキュー)

この記事で得られること

- ヒープキューを使った実装の練習

詳細

問題

原文

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.

1
2
3
4
5
6
7

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

1
2

Input: stones = [1]
Output: 1

Constraints:

1 <= stones.length <= 30

1 <= stones[i] <= 1000

内容(和訳)

整数の配列 stones が与えられ、stones[i] は i 番目の石の重さです。

石を使ってゲームをします。各ターンで、最も重い 2 つの石を選んでぶつけます。最も重い 2 つの石の重さが x と y で、x <= y とします。このぶつけの結果は、次のとおりです。

x == y の場合、両方の石が破壊されます。
x != y の場合、重さ x の石が破壊され、重さ y の石は新しい重さ y – x になります。ゲームの終了時には、残っている石は最大で 1 個です。

最後の残っている石の重さを返します。石が残っていない場合は 0 を返します。

※正しくない可能性があります。

解答

解答1：Python, iterative

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones.sort()
        while len(stones) > 1:
            y = stones.pop()
            x = stones.pop()
            if y==x: pass
            if y>x:
                y -= x
                stones.append(y)
                stones.sort()
            
        if len(stones)==0: return 0
        if len(stones)!=0: return stones[0]

class Solution:

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

stones.sort()

while len(stones) > 1:

y = stones.pop()

x = stones.pop()

if y==x: pass

if y>x:

y -= x

stones.append(y)

stones.sort()

if len(stones)==0: return 0

if len(stones)!=0: return stones[0]

解答2:Python, ヒープキュー(優先度付きキュー)

#優先度付きキュー
import heapq 

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        #負数にする
        for i, s in enumerate(stones):
            stones[i] = -s        
        #優先度付きキューに変換
        heapify(stones) 
        print(stones)
        #優先度付きキューに変換されたstonesに要素がある限り繰り返す
        while stones:
            #heappopは最小値を取り出す。-heappopで負数から正数に変換している。
            s1 = -heappop(stones)
            #stoensにもう要素がなければs1を返す
            if not stones: 
                return s1
            #s2に次の最大値を代入
            s2 = -heappop(stones)
            if s1 > s2:
                #s2-s1(s1-s2が負数になった値)を優先度付きキューに入れる
                heappush(stones, s2-s1)
        #stonesに要素がなければ0を返す
        return 0

#優先度付きキュー

import heapq

class Solution:

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

#負数にする

for i, s in enumerate(stones):

stones[i] = -s

#優先度付きキューに変換

heapify(stones)

print(stones)

#優先度付きキューに変換されたstonesに要素がある限り繰り返す

while stones:

#heappopは最小値を取り出す。-heappopで負数から正数に変換している。

s1 = -heappop(stones)

#stoensにもう要素がなければs1を返す

if not stones:

return s1

#s2に次の最大値を代入

s2 = -heappop(stones)

if s1 > s2:

#s2-s1(s1-s2が負数になった値)を優先度付きキューに入れる

heappush(stones, s2-s1)

#stonesに要素がなければ0を返す

return 0

ヒープキュー(優先度付きキュー)を始めて使ったのでメモ。

・ヒープキューは最小値をO(log(n))で取得できる。

・ヒープキューは要素をO(log(n))で挿入できる。

・Pythonにはheapqという標準ライブラリがある

・heapify(リスト)でヒープキューに変換できる

・ヒープキューへの変換時に昇順でソートされる。

・heappopでヒープキューの先頭要素(最小値)を取得

・Pythonのheapqライブラリには最大値の取得メソッドはない

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

疑問が解決した方は他の問題もどうぞ

前：231. Power of Two

次：1071. Greatest Common Divisor of Strings

LeetCode 解答・解説記事一覧