ゼロから始めるLeetCode Day111「682. Baseball Game」

• 概要
• 問題
• 解法

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回

ゼロから始めるLeetCode Day110「1535. Find the Winner of an Array Game」

次回
その内

Twitterやってます。

問題

682. Baseball Game
難易度はEasy。
久しぶりでいろいろ忘れているのでひとまずEasy
の問題を潰そうかなと思います。

問題としては、あなたは野球の試合に出場することになりました。このゲームはいくつかのラウンドで構成されており、過去のラウンドの得点が将来のラウンドの得点に影響を与える可能性があります。

ゲームの最初に、あなたは空のレコードで開始します。ops[i]はレコードに適用しなければならない第一の操作であり，以下のいずれかである．

整数 x - x の新しいスコアを記録します。
“+” - 前の2つのスコアの合計を新しいスコアとして記録します。前の 2 つのスコアが常に存在することが保証されています。
“D” - 前のスコアの2倍の新しいスコアを記録します。これは、常に前のスコアが存在することを保証します。
“C” - 前回のスコアを無効にし、記録から削除します。これは、常に前のスコアが存在することを保証するものです。
レコード上のすべてのスコアの合計を返します。

Example 1:
Input: ops = [“5”,“2”,“C”,“D”,"+"]
Output: 30
Explanation:
“5” - Add 5 to the record, record is now [5].
“2” - Add 2 to the record, record is now [5, 2].
“C” - Invalidate and remove the previous score, record is now [5].
“D” - Add 2 * 5 = 10 to the record, record is now [5, 10].
“+” - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

Example 2:
Input: ops = [“5”,"-2",“4”,“C”,“D”,“9”,"+","+"]
Output: 27
Explanation:
“5” - Add 5 to the record, record is now [5].
“-2” - Add -2 to the record, record is now [5, -2].
“4” - Add 4 to the record, record is now [5, -2, 4].
“C” - Invalidate and remove the previous score, record is now [5, -2].
“D” - Add 2 * -2 = -4 to the record, record is now [5, -2, -4].
“9” - Add 9 to the record, record is now [5, -2, -4, 9].
“+” - Add -4 + 9 = 5 to the record, record is now [5, -2, -4, 9, 5].
“+” - Add 9 + 5 = 14 to the record, record is now [5, -2, -4, 9, 5, 14].
The total sum is 5 + -2 + -4 + 9 + 5 + 14 = 27.

Example 3:
Input: ops = [“1”]
Output: 1

Constraints:

• 1 <= ops.length <= 1000
• ops[i] is "C", "D", "+", or a string representing an integer in the range [-3 * 104, 3 * 104].
• For operation "+", there will always be at least two previous scores on the record.
• For operations "C" and "D", there will always be at least one previous score on the record.

解法

class Solution:
    def calPoints(self, ops: List[str]) -> int:
        stack = []
        for s in ops:
            if s == "+":
                stack.append(stack[-1] + stack[-2])
            elif s == "C":
                stack.pop()
            elif s == "D":
                stack.append(stack[-1]*2)
            else:
                stack.append(int(s))
        return sum(stack)
Runtime: 36 ms, faster than  83.92%  of  Python3  online submissions for  Baseball Game.

Memory Usage: 14.2 MB, less than  92.17%  of  Python3  online submissions for  Baseball Game.

リハビリがてら適当に問題を選んで解きましたが、至って単純な分岐の問題でした。
それにしてもこういう問題を見ると逆ポーランド記法を思い出すのは私だけでしょうか。

個人的に読んでいてあ、これいいなと思ったのは以下の例。

class Solution:
    def calPoints(self, ops: List[str]) -> int:
        stack = []
        for op in ops:
            if(op not in "CD+"):
                stack.append(int(op))
            elif(op == "+"):
                stack.append(int(stack[-1]) + int(stack[-2]))
            elif(op == "D"):
                stack.append(int(stack[-1]) * 2)
            else:
                stack.pop()
        return sum(stack)

https://leetcode.com/problems/baseball-game/discuss/936778/Python3%3A-Using-Stack

この解答では数字の判定の部分を記述していますね。
僕は面倒くさそうな条件はelseで記述してしまえ、という考え方なので恐らくこういう記述法はしないと思いますが、仮に書くならこれがいいかなと思いました。

では今回はここまで。
お疲れ様でした。