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つのスコアがある場合にのみ
"+"が現れ、少なくとも1つある場合にのみ"D"と"C"が現れます。 - 記録上のすべてのスコアと最終的な合計は、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です。
発展問題
直近の"C"を取り消して、取り消されたスコアを戻す操作を、O(1)時間でどのように追加しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべてのルールは、最新のスコアまたは最新の2つのスコアについて説明しています。
"C"によって最新のスコアが削除されると、どうなるでしょうか？キャンセルすると、削除されたスコアの直前のスコアが再び最新になります。スコアは追加された順序と逆の順序で取り除かれます。これはスタックの動作と同じです。
新しいスコアはすべてスタックにプッシュします。スコアそのもの、
"D"の場合はスタックの一番上の値の2倍、"+"の場合は一番上の2つの値の合計です。"C"の場合はポップします。最後に、残った値の合計を返すか、プッシュやポップのたびに合計を更新します。
解説
各操作は最新のスコアを読み取り、"C"はそれらを1つずつ取り除くため、古いスコアが再び最新になります。これは後入れ先出しです。新しいスコアをそれぞれプッシュし、"C"ではポップして、"D"と"+"では一番上の1つまたは2つを読み取ります。
スタック上に記録を積み上げ、最後に合計する
考え方
最新のスコアが末尾になるように記録をリストとして保持し、各操作が末尾だけに触れるようにします。"C" の後は、2番目に新しいスコアが最新になり、その後の "D" または "+" はそのスコアを読み取る必要があります。末尾から取り除くと、それが現れます。最初の例では、"C" が -6 を取り除き、[4, -2, -4] が残ります。
操作がなくなったら、リストには数えるべきスコアだけが残るので、それらを合計します。時間計算量は 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 をスタックの合計と等しく保ちます。プッシュするたびに新しいスコアを加算し、"C" のたびにポップしたスコアを減算します。キャンセル時にどのスコアを取り除くか分かるように、スタックはそのまま残しておく必要があります。最初の例では、合計は 4, 2, -2, -8 と変化し、キャンセルによって -6 が取り除かれて -2 になり、7 を加えると 5 になります。
これは O(n) 時間の1回の走査で、操作のどの接頭部分に対しても答えが得られます。すべての操作が残る数値である可能性があるため、空間計算量は O(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つのスコアだけを保持する。
["1", "2", "3", "C", "+"]では、"+"には1と2が必要ですが、2つのスコアだけを保持すると1が失われます。 - 取り消したスコアを累計から差し引かない。2つ目の例では、その結果
0ではなく18になります。 - 数字が含まれているかどうかで、入力が数値かどうかを判断する。
"-2"はマイナス記号で始まります。3つの記号と照合し、それ以外はすべて言語の整数パーサーで解析してください。 - 答えは正の数だと思い込む。
["-3", "D"]の合計は-9です。
よくある質問3
Baseball Game の時間計算量は何ですか？
各操作はスタックの最上部で一定量の処理を行うため、n 回の操作には O(n) 時間がかかります。ほとんどの操作でスコアを追加する場合、スタックは O(n) の領域を使用します。
なぜスタックは野球ゲームに適したデータ構造なのでしょうか？
各ルールは、直近のスコアを読み取るか削除し、取り消すとその前のスコアが現れます。これは後入れ先出しであり、スタックを使えば、プッシュ、ポップ、ピークを O(1) で実行できます。末尾だけを使う配列は、スタックとして機能します。
Baseball Game は追加の O(1) 空間で解けますか？
一般にはそうではありません。数字が連続した後に "C" の項目が連続すると、逆順に取り消されるため、取り消されるかどうかがわかるまで、すべての数字を覚えておく必要があります。最悪の場合、O(n) のメモリが必要です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def calPoints(operations):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
operations = ["4", "-2", "D", "+", "C", "7"]
期待される出力
5