Baseball Game
あなたは風変わりなゲームのスコアを記録します。リスト operations は左から右に読み取られ、各項目によってスコア記録が変化します。"7" や "-2" のような整数は、そのスコアを記録に追加します。"+" は直近2つのスコアの合計を追加し、"D" は直近のスコアの2倍を追加し、"C" は直近のスコアを記録から完全に削除します。
最後の操作の後に記録に残っているスコアの合計を返す、calPoints という名前の関数を書いてください。記録が空の場合、合計は 0 です。
関数
- operationsstring-array
- 操作は順に、テキストとしての整数、または「+」、「D」、「C」
- 戻り値integer
- 最後に記録に残っているスコアの合計
制約
1 ≤ operations.length ≤ 5000- 各エントリーは
"+"、"D"、"C"、または-3 × 104 ≤ value ≤ 3 × 104の範囲で10進数表記された整数です。 - すべての操作は有効です。
"+"が来るのは記録にスコアが少なくとも2つある場合のみで、"D"と"C"が来るのは記録にスコアが少なくとも1つある場合のみです。 - 記録上のすべてのスコアと最終的な合計は、32 ビット符号付き整数に収まります。
例
- 入力
- operations = ["4", "-2", "D", "+", "C", "7"]
- 出力
- 5
- 説明
- 記録は
[4, -2]に増え、"D"は-4を追加し、"+"は-2 + -4 = -6を追加し、"C"はその-6を削除し、最後に7が加わります。記録[4, -2, -4, 7]の合計は5です。
- 入力
- operations = ["6", "D", "C", "C"]
- 出力
- 0
- 説明
"D"は6の後に12を追加し、その後、2つの"C"の項目が12と6を削除します。何も残らないため、答えは0です。
- 入力
- operations = ["1", "2", "+", "+", "D"]
- 出力
- 21
- 説明
- 2 つの
"+"エントリは1 + 2 = 3、続いて2 + 3 = 5を加算し、"D"は10を加算します。記録[1, 2, 3, 5, 10]の合計は21です。
提出時に隠しテスト+13件
発展問題
最後の記録を足し合わせずに合計を返して、キャンセルを含むすべての操作をO(1)時間で実行できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべてのルールは、最新のスコアまたは直近2つのスコアについて説明しています。
"C"で最新のスコアを削除すると、どうなるでしょうか？取り消し後、削除されたスコアの直前のスコアが再び最新になります。スコアは追加された順序と逆の順序で取り除かれます。これはスタックの動作と同じです。
新しいスコアはすべてスタックにプッシュします。数値そのもの、
"D"の場合はスタックの一番上の値の2倍、"+"の場合は上位2つの値の合計をプッシュします。"C"の場合はポップします。最後に残った値の合計を返すか、プッシュやポップのたびに合計を更新します。
解説
各操作は最新のスコアを参照し、"C"はスコアを1つずつ取り除けるため、取り消されたスコアより前のスコアが再び最新になります。この後入れ先出しのパターンは、まさにスタックです。新しいスコアを追加し、"C"のときに取り出し、"D"と"+"のときは先頭の1つまたは2つの要素を参照します。
スタック上に記録を作成し、最後に合計します
考え方
記録はリストとして保持し、最新のスコアが末尾に来るようにします。すると、各操作はリストの末尾だけを扱います。整数は追加し、"D"は最後の要素の2倍を追加し、"+"は最後の2つの要素の合計を追加し、"C"は最後の要素を取り除きます。
スタックで十分な理由は、"C"の後には、2番目に新しいスコアが最新のスコアになり、その後に続く"D"や"+"が読み取るのはそのスコアだからです。末尾から取り除けば、それを簡単に取得できます。最初の例では、"C"によって-6が取り除かれ、[4, -2, -4]が残ります。そのため、その後に"+"があれば、再び-2 + -4を加算します。
操作がなくなると、リストには集計対象のスコアだけが残ります。それらを合計します。各操作はO(1)で、最後の合計はO(n)です。そのため、スタックにO(n)の空間を使い、全体の実行時間はO(n)です。
アルゴリズム
- 空のスタック
recordから始めます。 "+"の場合は、上から2つの要素の合計をプッシュします。"D"の場合は、スタックの一番上の要素の2倍をプッシュします。"C"の場合は、一番上の要素をポップします。- それ以外の場合、要素は数値です。テキストを整数に変換してプッシュします。
- スタックに残っているすべての要素の合計を返します。
def calPoints(operations):
record = [] # the scores that still count, newest last
for op in operations:
if op == "+":
record.append(record[-1] + record[-2])
elif op == "D":
record.append(2 * record[-1])
elif op == "C":
record.pop()
else:
record.append(int(op))
return sum(record)累計値を持つスタック
考え方
スタックを最後に走査する処理は、避けられる余分な作業です。スタックの合計と常に等しくなる変数 total を保持します。プッシュするたびに新しいスコアを total に加算し、"C" のたびにポップしたスコアを減算します。
スタックは引き続き必要です。キャンセル時には、合計から取り消すスコアを把握する必要があり、"+" と "D" ではキャンセル後の最新のスコアを把握する必要があります。最初の例では合計が 4, 2, -2, -8 と変化し、その後キャンセルによって -6 が取り消されて -2 になり、最後の 7 を加えると 5 になります。
1回の走査で時間計算量は O(n) です。また、操作のどの接頭部分の後でも答えが得られるため、スコアがリアルタイムで届く場合に重要です。空間計算量は O(n) です。n 個すべての操作が、記録に残る数値である可能性があるためです。
アルゴリズム
- 空のスタック
recordとtotal = 0から始めます。 "C"の場合、トップのスコアを取り出し、totalから差し引きます。- それ以外の場合、新しいスコアを求めます。
"+"の場合は上位2つの合計、"D"の場合はトップの2倍、または整数そのものです。 - 新しいスコアをプッシュし、
totalに加えます。 totalを返します。
def calPoints(operations):
record = [] # the scores that still count, newest last
total = 0 # always the sum of record
for op in operations:
if op == "C":
total -= record.pop() # the cancelled score leaves the total too
continue
if op == "+":
score = record[-1] + record[-2]
elif op == "D":
score = 2 * record[-1]
else:
score = int(op)
record.append(score)
total += score
return total
落とし穴と境界ケース
ルールは簡単なので、バグの多くはスコアを読み違えたり、テキストを解析したりするときに発生します。
- 累積合計と直近2つのスコアだけを保持する。
"C"の後にはその2つより前のスコアが必要になるため、取り消しの後に"+"が続くと古い値を読み取ってしまいます。スタック全体を保持してください。 - 取り消されたスコアも合計から差し引くことを忘れる。累積合計を使う場合、
"C"では取り出したスコアを無視するのではなく、差し引く必要があります。 - 負のスコアを手作業で解析して、符号を落としてしまう。言語の整数パーサーを使えば、
"-2"を-2として読み取れます。 - 項目が数値かどうかを判断するために、数字かどうかを調べる。
"-5"はマイナス記号で始まります。3つの記号をチェックし、それ以外はすべて数値として扱ってください。 - 答えが正の数だと思い込む。負のスコアや取り消しによって合計が負になることも、すべてのスコアが取り消されて
0になることもあります。
よくある質問4
Baseball Game の時間計算量は何ですか？
各操作はスタックの先頭で一定量の処理を行うため、n 個の操作を処理するには O(n) 時間がかかります。最後にスタックの合計を計算する処理も最大でさらに O(n) かかりますが、累計を保持すればこの処理も不要になります。ほとんどの操作でスコアを追加する場合、スタックは O(n) の領域を使用します。
なぜスタックは Baseball Game に適したデータ構造なのでしょうか？
各ルールは直近のスコアを読み取るか削除し、取り消すとその前のスコアが表に出ます。これは後入れ先出しの順序であり、スタックなら O(1) で push、pop、peek を行えます。末尾だけを使う通常の配列やリストは、どの言語でもスタックとして機能します。
野球ゲームは追加の空間計算量 O(1) で解けますか？
一般にはそうではありません。数字が連続した後に "C" の項目が連続すると、数字は逆順に取り消されます。そのため、取り消されるかどうかが分かるまで、すべての数字を覚えておく必要があります。最悪の場合、O(n) のメモリが必要です。累計を使えば最後の処理は省けますが、スタックの代わりにはなりません。
Baseball Gameでは、数値と演算をどう見分けますか？
まずエントリを3つの記号 "+"、"D"、"C" と比較し、それ以外は整数として扱います。言語のパーサーで変換すると先頭のマイナス記号も処理されるため、"-30000" は -30000 になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def calPoints(operations):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
operations = ["4", "-2", "D", "+", "C", "7"]
期待値
5