[LeetCode] 682. Baseball Game 棒球游戏

2021年09月15日 阅读数:3
这篇文章主要向大家介绍[LeetCode] 682. Baseball Game 棒球游戏,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

You're now a baseball game point recorder.html

Given a list of strings, each string can be one of the 4 following types:java

  1. Integer (one round's score): Directly represents the number of points you get in this round.
  2. "+" (one round's score): Represents that the points you get in this round are the sum of the last two valid round's points.
  3. "D" (one round's score): Represents that the points you get in this round are the doubled data of the last valid round's points.
  4. "C" (an operation, which isn't a round's score): Represents the last valid round's points you get were invalid and should be removed.

 

Each round's operation is permanent and could have an impact on the round before and the round after.python

You need to return the sum of the points you could get in all the rounds.app

Example 1:post

Input: ["5","2","C","D","+"]
Output: 30
Explanation: 
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get 2 points. The sum is: 7.
Operation 1: The round 2's data was invalid. The sum is: 5.  
Round 3: You could get 10 points (the round 2's data has been removed). The sum is: 15.
Round 4: You could get 5 + 10 = 15 points. The sum is: 30.

Example 2:this

Input: ["5","-2","4","C","D","9","+","+"]
Output: 27
Explanation: 
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get -2 points. The sum is: 3.
Round 3: You could get 4 points. The sum is: 7.
Operation 1: The round 3's data is invalid. The sum is: 3.  
Round 4: You could get -4 points (the round 3's data has been removed). The sum is: -1.
Round 5: You could get 9 points. The sum is: 8.
Round 6: You could get -4 + 9 = 5 points. The sum is 13.
Round 7: You could get 9 + 5 = 14 points. The sum is 27.

Note:url

  • The size of the input list will be between 1 and 1000.
  • Every integer represented in the list will be between -30000 and 30000.

解法:栈,用一个stack记录,循环字符串,若是是数字直接进栈,若是当前字符是操做符对栈里面的数字进行相应处理,'+'把栈里面最后两个数字相加而后如栈,'D'把栈里的最后一个数字乘以2而后如栈,'C'移除栈里面的最后一个元素。最后返回栈里全部元素的和。code

Java:htm

class Solution {
    public int calPoints(String[] ops) {
        int sum = 0;
        LinkedList<Integer> list = new LinkedList<>();
        for (String op : ops) {
            if (op.equals("C")) {
                sum -= list.removeLast();
            }
            else if (op.equals("D")) {
                list.add(list.peekLast() * 2);
                sum += list.peekLast();
            }
            else if (op.equals("+")) {
                list.add(list.peekLast() + list.get(list.size() - 2));
                sum += list.peekLast();
            }
            else {
                list.add(Integer.parseInt(op));
                sum += list.peekLast();
            }
        }
        return sum;
    }
}  

Python:blog

class Solution(object):
    def calPoints(self, ops):
        """
        :type ops: List[str]
        :rtype: int
        """
        history = []
        for op in ops:
            if op == '+':
                history.append(history[-1] + history[-2])
            elif op == 'D':
                history.append(history[-1] * 2)
            elif op == 'C':
                history.pop()
            else:
                history.append(int(op))
        return sum(history)  

C++:

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

  

 

All LeetCode Questions List 题目汇总