Skip to content

LeetCode: 682-Baseball Game 解題紀錄

Last Updated on 2022-04-10 by Clay

題目

You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds' scores.

At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following:

  1. An integer x - Record a new score of x.
  2. "+" - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores.
  3. "D" - Record a new score that is double the previous score. It is guaranteed there will always be a previous score.
  4. "C" - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score.

Return the sum of all the scores on the record.

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.

（這題在 LeetCode 上算是我少見地看到負評遠比正評來得多的題目。我並不確定原因為何，但我想是因為幾乎只有寫規則一種解法？）

題目會給一串紀錄符號，讓我們替棒球比賽做紀錄。

  • 如果是數字，則代表當前新回合的分數
  • 如果是 +，則把前兩回合的分數加總成新回合的分數
  • 如果是 D，則把前一個數字的分數乘以二變成新回合的分數
  • 如果是 C，則把前一回合的分數取消

解題紀錄

暴力法，寫規則，無論是時間複雜度還是空間複雜度都是 O(n)。

C++ 範例程式碼

class Solution {
public:
    int calPoints(vector<string>& ops) {
        // Init
        vector<int> scores;
        
        // Record
        for (auto& op: ops) {
            if (op == "C") {
                scores.pop_back();
            }
            else if (op == "D") {
                scores.push_back(scores.back()*2);
            }
            else if (op == "+") {
                scores.push_back(scores.back()+scores[scores.size()-2]);
            }
            else {
                scores.push_back(std::stoi(op));
            }
        }
        
        // Sum
        return std::accumulate(scores.begin(), scores.end(), 0);
    }
};



Python 範例程式碼

class Solution:
    def calPoints(self, ops: List[str]) -> int:
        # Init
        scores = []
        
        # Record
        for op in ops:
            if op == "C":
                scores.pop()
            elif op == "D":
                scores.append(scores[-1]*2)
            elif op == "+":
                scores.append(sum(scores[-2:]))
            else:
                scores.append(int(op))
        
        # Sum
        return sum(scores)

References

Read More

Tags:

Leave a Reply