| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
Easy |
|
You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.
You are given a list of strings operations, where operations[i] is the ith operation you must apply to the record and is one of the following:
- An integer
x.<ul> <li>Record a new score of <code>x</code>.</li> </ul> </li> <li><code>'+'</code>. <ul> <li>Record a new score that is the sum of the previous two scores.</li> </ul> </li> <li><code>'D'</code>. <ul> <li>Record a new score that is the double of the previous score.</li> </ul> </li> <li><code>'C'</code>. <ul> <li>Invalidate the previous score, removing it from the record.</li> </ul> </li>
Return the sum of all the scores on the record after applying all the operations.
The test cases are generated such that the answer and all intermediate calculations fit in a 32-bit integer and that all operations are valid.
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","C"] Output: 0 Explanation: "1" - Add 1 to the record, record is now [1]. "C" - Invalidate and remove the previous score, record is now []. Since the record is empty, the total sum is 0.
Constraints:
1 <= operations.length <= 1000operations[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.
We can use a stack to simulate this process.
Traverse
- If it is
+, add the top two elements of the stack and push the result onto the stack; - If it is
D, multiply the top element of the stack by 2 and push the result onto the stack; - If it is
C, pop the top element of the stack; - If it is a number, push the number onto the stack.
Finally, sum all the elements in the stack to get the answer.
The time complexity is
class Solution:
def calPoints(self, operations: List[str]) -> int:
stk = []
for op in operations:
if op == "+":
stk.append(stk[-1] + stk[-2])
elif op == "D":
stk.append(stk[-1] << 1)
elif op == "C":
stk.pop()
else:
stk.append(int(op))
return sum(stk)class Solution {
public int calPoints(String[] operations) {
Deque<Integer> stk = new ArrayDeque<>();
for (String op : operations) {
if ("+".equals(op)) {
int a = stk.pop();
int b = stk.peek();
stk.push(a);
stk.push(a + b);
} else if ("D".equals(op)) {
stk.push(stk.peek() << 1);
} else if ("C".equals(op)) {
stk.pop();
} else {
stk.push(Integer.valueOf(op));
}
}
return stk.stream().mapToInt(Integer::intValue).sum();
}
}class Solution {
public:
int calPoints(vector<string>& operations) {
vector<int> stk;
for (auto& op : operations) {
int n = stk.size();
if (op == "+") {
stk.push_back(stk[n - 1] + stk[n - 2]);
} else if (op == "D") {
stk.push_back(stk[n - 1] << 1);
} else if (op == "C") {
stk.pop_back();
} else {
stk.push_back(stoi(op));
}
}
return accumulate(stk.begin(), stk.end(), 0);
}
};func calPoints(operations []string) (ans int) {
var stk []int
for _, op := range operations {
n := len(stk)
switch op {
case "+":
stk = append(stk, stk[n-1]+stk[n-2])
case "D":
stk = append(stk, stk[n-1]*2)
case "C":
stk = stk[:n-1]
default:
num, _ := strconv.Atoi(op)
stk = append(stk, num)
}
}
for _, x := range stk {
ans += x
}
return
}function calPoints(operations: string[]): number {
const stk: number[] = [];
for (const op of operations) {
if (op === '+') {
stk.push(stk.at(-1)! + stk.at(-2)!);
} else if (op === 'D') {
stk.push(stk.at(-1)! << 1);
} else if (op === 'C') {
stk.pop();
} else {
stk.push(+op);
}
}
return stk.reduce((a, b) => a + b, 0);
}impl Solution {
pub fn cal_points(operations: Vec<String>) -> i32 {
let mut stk = vec![];
for op in operations {
match op.as_str() {
"+" => {
let n = stk.len();
stk.push(stk[n - 1] + stk[n - 2]);
}
"D" => {
stk.push(stk.last().unwrap() * 2);
}
"C" => {
stk.pop();
}
n => {
stk.push(n.parse::<i32>().unwrap());
}
}
}
stk.into_iter().sum()
}
}