Sweaty Imposter

Baseball Game

EasyStackJuniorOpen on LeetCodeUpdated

You're keeping score for a game with unusual rules, given as a list of string operations applied in order to an empty record. An integer x records a new score of x. "+" records a new score equal to the sum of the previous two scores. "D" records double the previous score. "C" removes the previous score from the record. Return the sum of the scores left on the record after every operation. Every operation is valid when it runs.

Examples

operations = ["5","2","C","D","+"] returns 30

The record goes [5], then [5,2]. "C" removes the 2, "D" adds 10, and "+" adds 5 + 10 = 15, leaving [5,10,15], which sums to 30.

operations = ["5","-2","4","C","D","9","+","+"] returns 27

"C" removes the 4, "D" doubles -2 into -4, then 9 is recorded. The first "+" adds -4 + 9 = 5 and the second adds 9 + 5 = 14. The record [5,-2,-4,9,5,14] sums to 27.

operations = ["1","C"] returns 0

"C" removes the only score, so the record is empty and sums to 0.

Constraints

  • 1 <= operations.length <= 1000
  • operations[i] is "C", "D", "+", or an integer in the range [-3 * 10^4, 3 * 10^4].
  • "+" always has at least two previous scores, and "C" and "D" always have at least one.
  • Every intermediate score and the final sum fit in a 32-bit integer.

Hints

Hint 1

Every operation only looks at the newest scores, and one of them undoes the newest. What structure fits that?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Every rule reads or removes only the most recent scores, and "C" undoes the latest one, so the record behaves like a stack. Push each integer, push twice the top for "D", push the sum of the top two for "+", and pop for "C". When the operations run out, add up whatever is left on the stack.

Time

O(n)

Space

O(n)

Pitfall

"+" adds a score without removing the two it reads: popping both to add them and pushing back only the sum erases them from the record. Also check for the three symbols before parsing a number, because a digit test like isdigit rejects negative scores such as "-2".

Solutions

class Solution {
    public int calPoints(String[] operations) {
        List<Integer> stack = new ArrayList<>();
        for (String op : operations) {
            int n = stack.size();
            switch (op) {
                case "+" -> stack.add(stack.get(n - 1) + stack.get(n - 2));
                case "D" -> stack.add(stack.get(n - 1) * 2);
                case "C" -> stack.remove(n - 1);
                default -> stack.add(Integer.parseInt(op));
            }
        }
        int total = 0;
        for (int score : stack) total += score;
        return total;
    }
}
Drill This