Sponsored
Sponsored
This approach involves using a stack (or list) to simulate the score record. Each operation determines how you transform the record:
After processing all operations, sum up the stack to get the total score.
Time Complexity: O(n), where n is the number of operations.
Space Complexity: O(n), for the storage of scores in the stack.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int calPoints(char** ops, int opsSize) {
6 int stack[1000];
7 int top = -1;
8 for (int i = 0; i < opsSize; i++) {
9 if (strcmp(ops[i], "+") == 0) {
10 stack[++top] = stack[top] + stack[top - 1];
11 } else if (strcmp(ops[i], "D") == 0) {
12 stack[++top] = 2 * stack[top];
13 } else if (strcmp(ops[i], "C") == 0) {
14 top--;
15 } else {
16 stack[++top] = atoi(ops[i]);
17 }
18 }
19 int sum = 0;
20 for (int i = 0; i <= top; i++) {
21 sum += stack[i];
22 }
23 return sum;
24}We use an array to implement a stack. Integer operations update the stack, and we maintain a top pointer to keep track of the current top.
This approach leverages in-place list manipulation without using any explicit stack. Use a low-level list operation to track the scores and operations similar to calcualtions within the same list. Ideal for scripting languages that optimize list operations.
Time Complexity: O(n).
Space Complexity: O(n) due to maintaining result list as stack.
1def calPoints(ops):
2 record = []
3 for op in opsInstead of a designated stack, the list itself is used to apply operations which may concatenate new scores or remove past ones. The final sum is the sum of list elements.