682. Baseball gamesTopic description
Difficulty: easy
You are now the scorer for a special game baseball game. The game consists of several rounds, and the scores of the past rounds may affect the scores of the later rounds.
When the game started, the record was blank. you will get a string list ops that records the operations, where ops[i] is the i-th operation you need to log, ops follows the rules:
1. Integer x – Indicates the new score x obtained in this round
2. “+” – means that the new score in this round is the sum of the previous two scores. The item data guarantees that there are always two valid scores preceding this action when it is recorded.
3. “D” – Indicates that the new score in this round is double the previous score. The item data guarantees that a valid score is always present before this action is recorded.
4. “C” – Indicates that the previous score was invalid and removed from the record. The item data guarantees that a valid score is always present before this action is recorded.
Please return the sum of all scores in the record.
Example 1:
输入：ops = ["5","2","C","D","+"]
输出：30
解释：
"5" - 记录加 5 ，记录现在是 [5]
"2" - 记录加 2 ，记录现在是 [5, 2]
"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5].
"D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10].
"+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].
所有得分的总和 5 + 10 + 15 = 30Example 2:
输入：ops = ["5","-2","4","C","D","9","+","+"]
输出：27
解释：
"5" - 记录加 5 ，记录现在是 [5]
"-2" - 记录加 -2 ，记录现在是 [5, -2]
"4" - 记录加 4 ，记录现在是 [5, -2, 4]
"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5, -2]
"D" - 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4]
"9" - 记录加 9 ，记录现在是 [5, -2, -4, 9]
"+" - 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5]
"+" - 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14]
所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27Example 3:
输入：ops = ["1"]
输出：1hint:
- 1 <= ops.length <= 1000
- ops[i] is “C”, “D”, “+”, or a string representing an integer.The integer range is [-3 * 104, 3 * 104]
- For the “+” operation, the item data guarantees that there are always two valid scores preceding this operation when it is recorded
- For “C” and “D” actions, the item data guarantees that a valid score is always present before this action is recorded
solution
Method 1: Simulation
Ideas and Algorithms
The stack is simulated using a variable-length array.
- If the operation is +, then access the last two scores of the array, add the sum of the two scores to the total score, and push the sum of the two scores onto the stack.
- If the operation is D, then the last score of the array is accessed, the score multiplied by 2 is added to the total score, and the score multiplied by 2 is pushed onto the stack.
- If the operation is C, then the last score of the array is accessed, the score is subtracted from the total score, and the score is popped from the stack.
- If the operation is an integer, add the integer to the total score and push the integer onto the stack.
code
Python3
class Solution:
def calPoints(self, ops: List[str]) -> int:
ans = 0
points = []
for op in ops:
if op == '+':
pt = points[-1] + points[-2]
elif op == 'D':
pt = points[-1] * 2
elif op == 'C':
ans -= points.pop()
continue
else:
pt = int(op)
ans += pt
points.append(pt)
return ansC++
class Solution {
public:
int calPoints(vector& ops) {
int ret = 0;
vector points;
for (auto &op : ops) {
int n = points.size();
switch (op[0]) {
case '+':
ret += points[n - 1] + points[n - 2];
points.push_back(points[n - 1] + points[n - 2]);
break;
case 'D':
ret += 2 * points[n - 1];
points.push_back(2 * points[n - 1]);
break;
case 'C':
ret -= points[n - 1];
points.pop_back();
break;
default:
ret += stoi(op);
points.push_back(stoi(op));
break;
}
}
return ret;
}
}; Java
class Solution {
public int calPoints(String[] ops) {
int ret = 0;
List points = new ArrayList();
for (String op : ops) {
int n = points.size();
switch (op.charAt(0)) {
case '+':
ret += points.get(n - 1) + points.get(n - 2);
points.add(points.get(n - 1) + points.get(n - 2));
break;
case 'D':
ret += 2 * points.get(n - 1);
points.add(2 * points.get(n - 1));
break;
case 'C':
ret -= points.get(n - 1);
points.remove(n - 1);
break;
default:
ret += Integer.parseInt(op);
points.add(Integer.parseInt(op));
break;
}
}
return ret;
}
} C#
public class Solution {
public int CalPoints(string[] ops) {
int ret = 0;
IList points = new List();
foreach (string op in ops) {
int n = points.Count;
switch (op[0]) {
case '+':
ret += points[n - 1] + points[n - 2];
points.Add(points[n - 1] + points[n - 2]);
break;
case 'D':
ret += 2 * points[n - 1];
points.Add(2 * points[n - 1]);
break;
case 'C':
ret -= points[n - 1];
points.RemoveAt(n - 1);
break;
default:
ret += int.Parse(op);
points.Add(int.Parse(op));
break;
}
}
return ret;
}
} C
int calPoints(char ** ops, int opsSize){
int ret = 0;
int * points = (int *)malloc(sizeof(int) * opsSize);
int pos = 0;
for (int i = 0; i < opsSize; i++) {
switch (ops[i][0]) {
case '+':
ret += points[pos - 1] + points[pos - 2];
points[pos++] = points[pos - 1] + points[pos - 2];
break;
case 'D':
ret += 2 * points[pos - 1];
points[pos++] = 2 * points[pos - 1];
break;
case 'C':
ret -= points[pos - 1];
pos--;
break;
default:
ret += atoi(ops[i]);
points[pos++] = atoi(ops[i]);
break;
}
}
free(points);
return ret;
}JavaScript
var calPoints = function(ops) {
let ret = 0;
const points = [];
for (const op of ops) {
const n = points.length;
switch (op[0]) {
case '+':
ret += points[n - 1] + points[n - 2];
points.push(points[n - 1] + points[n - 2]);
break;
case 'D':
ret += 2 * points[n - 1];
points.push(2 * points[n - 1]);
break;
case 'C':
ret -= points[n - 1];
points.pop();
break;
default:
ret += parseInt(op);
points.push(parseInt(op));
break;
}
}
return ret;
};Golang
func calPoints(ops []string) (ans int) {
points := []int{}
for _, op := range ops {
n := len(points)
switch op[0] {
case '+':
ans += points[n-1] + points[n-2]
points = append(points, points[n-1]+points[n-2])
case 'D':
ans += points[n-1] * 2
points = append(points, 2*points[n-1])
case 'C':
ans -= points[n-1]
points = points[:len(points)-1]
default:
pt, _ := strconv.Atoi(op)
ans += pt
points = append(points, pt)
}
}
return
}Complexity Analysis
- Time complexity: O(n), where n is the size of the array ops. Traversing the entire ops takes O(n).
- Space complexity: O(n). A variable-length array can hold at most O(n) elements.
BY /
Author of this article: Likou
Disclaimer: This article is copyrighted by "Likou", if you need to reprint, please contact.
