+1-5714784200

Similar Problems

Similar Problems not available

Baseball Game - Leetcode Solution

Companies:

LeetCode:  Baseball Game Leetcode Solution

Difficulty: Easy

Topics: stack array simulation  

Baseball Game

Link

You’re now a baseball game point recorder.

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

  • Integer (one round’s score): Directly represents the number of points you get in this round.
  • “+” (one round’s score): Represents that the points you get in this round are the sum of the last two valid round’s points.
  • “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.
  • “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.

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

Example 1:

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.

Note:

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

The Baseball Game problem on LeetCode is a simple problem that involves simulating a baseball game and calculating the total score of a player. Here is a detailed solution to the problem:

Problem Description: You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of each round are represented by a list of strings. The valid options for a score are:

  1. An integer, which represents the number of points earned in this round.
  2. "+" which represents the number of points earned in this round as the sum of the last two valid round scores.
  3. "D" which represents the number of points earned in this round as twice the last valid round score.
  4. "C" which represents the removal of the last valid round score.

You need to return the total score of the player after all the rounds.

Solution: To solve this problem, we will use a stack to keep track of the valid scores. For each score in the list of scores, we will perform the following actions:

  1. If the score is an integer, push it onto the stack and add it to the running total of the score.
  2. If the score is "+", pop the last two scores from the stack, sum them, and push the sum onto the stack. Then add the sum to the running total of the score.
  3. If the score is "D", double the last score in the stack, push the double onto the stack, and add it to the running total of the score.
  4. If the score is "C", pop the last score from the stack and subtract it from the running total of the score.

After iterating through all the scores, the running total of the score will be the total score of the player.

Here is the Python implementation of the above solution:

def calPoints(self, ops: List[str]) -> int: stack = [] score = 0 for op in ops: if op.isdigit() or op[0] == "-": stack.append(int(op)) score += int(op) elif op == "+": last1 = stack.pop() last2 = stack.pop() curr = last1 + last2 stack.append(last2) stack.append(last1) stack.append(curr) score += curr elif op == "D": last = stack.pop() curr = 2 * last stack.append(last) stack.append(curr) score += curr elif op == "C": last = stack.pop() score -= last return score

Time Complexity: The time complexity of this solution is O(n) where n is the number of scores.

Space Complexity: The space complexity of this solution is also O(n) as we are using a stack to keep track of the valid scores.

Overall, this is an efficient solution to the Baseball Game problem on LeetCode.

Baseball Game Solution Code

1