Last Stone Weight
石の山があり、stones[i]は石iの重さです。各ラウンドで、最も重い2つの石を取り出してぶつけます。重さが同じなら、両方とも破壊されます。異なる場合は、軽い方が破壊され、重い方は2つの重さの差だけ小さくなります。
高々1つの石が残るまでラウンドを繰り返し、その重さを返すlastStoneWeightを作成してください。石が残っていない場合は0を返します。
関数
- stonesinteger-array
- 山の中の石の重さ
- 戻り値integer
- 最後の石の重さ、または石が残っていない場合は 0
制約
1 ≤ stones.length ≤ 1041 ≤ stones[i] ≤ 1000
例
- 入力
- stones = [3, 9, 4, 6, 2]
- 出力
- 0
- 説明
9と6から3が残り、次に4と3から1が残り、さらに3と2からもうひとつの1が残ります。2つの1の石は互いに破壊し合うため、答えは0です。
- 入力
- stones = [10, 4, 1]
- 出力
- 5
- 説明
10と4からは6が残り、6と1からは5が残ります。石が 1 つ残り、その重さは5です。
- 入力
- stones = [8]
- 出力
- 8
- 説明
- 石が1つだけではぶつける相手がいないため、その重さである
8が答えです。
発展問題
重さは最大で1000です。この上限を利用して、ヒープを使わずに O(n + W) 時間で解けますか？ここで W は最大の重さです。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
説明されているとおりにラウンドをプレイしましょう。各ラウンドの開始時に、すばやく見つける必要があるものは何ですか？
各ラウンドでは最も重い石が2つ必要で、戻す石は山にすでにある石より軽くなることがあります。新しい値が追加された後も常に最大の値を把握できるデータ構造があれば、再度ソートせずに済みます。
すべての石を最大ヒープに入れます。2回取り出し、差が0でない場合はその差を追加し、石が1個以下になるまで繰り返します。残った石、または
0を返します。
解説
先に進むための公式はありません。すべてのラウンドをプレイします。砕かれた石は軽くなって戻ってくることがあるため、各ラウンドでは変化し続ける山から最も重い石を2つ選ぶ必要があります。最大ヒープを使えば、最も重い石を取り出し、新しい石を戻す操作を O(log n) で行えます。
各ラウンドで山を並べ替える
正しいが、最大のテストでは終わらない
考え方
ルールに忠実に従います。石の山をソートし、末尾から最も重い石を2つ取り出し、その差がゼロでなければ戻します。差はどこにでも入り得るため、ラウンドごとに再度ソートします。最初の例では、9 と 6 を取り出すと 3 が残り、これは 4 より前に入ります。
各ラウンドで少なくとも1個の石が取り除かれるため、ラウンド数は最大で n-1 回です。各回で最大 n 個の石をソートするので、計算量は O(n² log n) です。n = 10^4 の場合、最大 10^4 個の数値を約 10^4 回ソートすることになります。
アルゴリズム
- 石を
pileというリストにコピーします。 - 石が1個より多く残っている間、昇順に並べ替えます。
- 最後の2個の石、
heaviestとsecondを取り出します。 - それらの重さが異なる場合は、
heaviest - secondを pile に戻します。 - 残った石を返します。pile が空の場合は
0を返します。
def lastStoneWeight(stones):
pile = list(stones)
while len(pile) > 1:
pile.sort() # the two heaviest stones move to the end
heaviest = pile.pop()
second = pile.pop()
if heaviest != second:
pile.append(heaviest - second)
return pile[0] if pile else 0最大ヒープ
考え方
最大ヒープでは最大値が先頭にあり、先頭の値を取り出したり値を追加したりするコストは O(log n) です。すべての石をヒープに入れます。各ラウンドでは、最も重い2つを取り出すために2回ポップし、差が0でなければその差をヒープに戻します。ヒープが適切な位置に移動させます。[10, 4, 1] の場合、10 と 4 を取り出して 6 を追加し、次に 6 と 1 を取り出して 5 を追加します。
2回のポップと1回の追加を行うラウンドは最大 n-1 回なので、時間計算量は O(n log n)、空間計算量は O(n) です。組み込みのヒープがない言語では、解法は配列でヒープを保持し、インデックス i の親は (i-1)/2 にあります。
アルゴリズム
- すべての石を最大ヒープに入れます。
- ヒープに石が1個より多くある間、最も重い石を取り出し、次に2番目に重い石を取り出します。
- 重さが異なる場合は、
heaviest - secondを追加します。 - ヒープが空の場合は
0を返し、そうでなければヒープの先頭を返します。
import heapq
def lastStoneWeight(stones):
# heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
heap = [-w for w in stones]
heapq.heapify(heap)
while len(heap) > 1:
heaviest = -heapq.heappop(heap)
second = -heapq.heappop(heap)
if heaviest != second:
heapq.heappush(heap, -(heaviest - second))
return -heap[0] if heap else 0
落とし穴と境界ケース
- 空の山の先頭を取り出そうとする。最初の例のように最後の2つの石の重さが同じ場合、何も残らず、答えは
0です。 - 誤って最小ヒープを使う。Python の
heapqと Java のデフォルトのPriorityQueueは最小の値を取り出すため、重さの符号を反転するか、逆順の比較関数を渡します。 - 重さの符号を反転したときに、結果の符号を忘れる。取り出した値はどちらも負なので、追加する値は
-(heaviest - second)です。 - 最初に一度だけソートして、そのままリストを順に処理する。差はまだ取り出していない石より軽いことがあるため、最初のラウンドの後には順序が古くなります。
よくある質問3
Last Stone Weight の時間計算量は何ですか？
最大ヒープを使うと、最大でも n-1 回のラウンドで、2 回のポップと 1 回のプッシュを行うため、時間計算量は O(n log n)、空間計算量は O(n) です。ラウンドごとに山全体をソートすると、時間計算量は O(n² log n) になります。
Last Stone Weight でソート済みリストではなくヒープを使うのはなぜですか？
ソート済みリストなら最も重い石を2つ同時に取り出せますが、差を戻して順序を整えるには最大でn個の要素を移動させる必要があり、全ラウンドではO(n²)かかります。ヒープは「最大値はどれか」を返し、新しい値を追加する操作をどちらもO(log n)で行えます。シミュレーションに必要なのはこれだけです。
同じ重さの石を砕く順番によって、答えは変わりますか？
いいえ。最も重い重さの石が複数ある場合、どちらを選んでも選んだ2つの石の重さは同じなので、ラウンド後に残る山の重さも同じです。答えは重さだけで決まります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def lastStoneWeight(stones):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
stones = [3, 9, 4, 6, 2]
期待される出力
0