Straightforward Python


  • 12
    W

    It not stated in the question but you can assume there is not invalid operations, such as C when the points history is empty, it still passed.

    class Solution(object):
        def calPoints(self, ops):
            # Time: O(n)
            # Space: O(n)
            history = []
            for op in ops:
                if op == 'C':
                    history.pop()
                elif op == 'D':
                    history.append(history[-1] * 2)
                elif op == '+':
                    history.append(history[-1] + history[-2])
                else:
                    history.append(int(op))
            return sum(history)
    
    

  • 1

    Hi @wanling, I came up with a very similar solution in C++. I agree with you, that it is more simple and efficient to calculate the sum after the entire string has been processed, rather than keeping track of a running total. Since the calculations for the running total could be all for nothing, if we end up invalidating all (or a significant portion) of the input using op "C".

    Also, I've had great success rates following the advice I found from @StefanPochmann, specifically: "Knowing and using library functions can do miracles for you. It's fast to use them and they probably don't have bugs."
    ( http://www.stefan-pochmann.info/spots/tutorials/basic_programming/ ). I'd like to dedicate this solution to Stefan, thanks so much Stefan for continually sharing your quality of thought!

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

  • 0
    F

    Good logic. But could be more preventive.

    With operation C, you need to make sure your stack is not empty before doing pop. Otherwise, you will receive IndexError

    With D and + operation, you can go out of range and get IndexError.


  • 0

    @Free9 thanks, I agree with you... actually I had a try/catch in my original code, I removed it to see if there were any invalid input test cases, and there are none. In a real-world use case, definitely I would have kept it. For LeetCode purposes, it can be distracting to add checks for invalid input.


  • 5
    T

    Simply add two 0 at the left of the input list would solve this problem.


  • 0
    W

    @tndstone That's a good idea! 😃


  • 0
    L

    @wanling The question should state clearly that C won't appear when there's no valid points, and + won't appear when there're not enough valid points. I was worried about the same thing when I hit submit.


  • 0
    S

    Same approach in Java-

      public int calPoints(String[] ops) {
        Stack<Integer> stack = new Stack<>();
        for (String op : ops) {
            if (op.equals("C")) {
                stack.pop();
            }
    
            else if (op.equals("D")) {
                stack.push(2 * stack.peek());
            }
    
            else if (op.equals("+")) {
                int sum = stack.get(stack.size()-1) + stack.get(stack.size()-2);
                stack.push(sum);
            }
            else {
                stack.push(Integer.valueOf(op));
            }
        }
    
        Integer sum = stack.stream().mapToInt(i -> i).sum();
    
        // Or
        // sum = stack.parallelStream().reduce(0, Integer::sum);
        return sum;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.