Understanding the Problem: 682. Baseball Game

Asked 3 months ago

0Comments

0 Views

What Does the Problem Ask?

In this problem, you're simulating a baseball game, where every action is recorded as a string in a list called operations. Each string can represent one of the following actions:

An Integer (e.g., "5"): This means you earned 5 points in this round.
"C": This indicates that the last round’s score is invalid, so you remove it.
"D": This indicates that you earned double the points of the last valid round.
"+": This indicates that you earned the sum of the last two valid rounds.

The task is to return the total score after all operations are performed.

How Do We Approach It?

Let's break down the steps and intuition behind solving this problem.

Use a Stack (or Vector in C++):
- A stack-like structure allows us to efficiently manage the points. We can add points, remove the last round’s points, or sum the last two rounds.
- We'll use a vector to store the valid scores.
Iterate Over Operations:
- For each operation, we’ll decide if we should add a score, double the last score, sum the last two scores, or cancel the previous score.
Summing the Scores:
- After processing all operations, we simply sum up all the valid scores in the vector.

Step-by-Step Intuition:

Start with an Empty Vector:
- This vector will store all valid points.
Loop Through the Operations:
- If you see a number (like "5"), convert it to an integer and push it to the vector.
- If you encounter a "C", simply pop the last element from the vector (i.e., remove the last round’s score).
- If you encounter a "D", take the last score, double it, and add it to the vector.
- If you encounter a "+", sum the last two valid scores and add that to the vector.
Final Score Calculation:
- At the end, sum up all the elements in the vector to get the final score.

The Code Implementation:

Here's how the solution looks in C++:

using namespace std;
#include <iostream>
#include <vector>

class Solution
{
public:
    int calPoints(vector<string> &operations)
    {
        vector<int> ans; // Vector to store valid points

        for (int i = 0; i < operations.size(); i++)
        {
            // If operation is "C", remove the last valid score
            if (operations[i] == "C")
            {
                ans.pop_back();
            }
            // If operation is "D", double the last score and add it to the vector
            else if (operations[i] == "D")
            {
                int temp = 2 * ans.back(); // Double the last valid score
                ans.push_back(temp);
            }
            // If operation is "+", add the sum of the last two scores
            else if (operations[i] == "+")
            {
                int temp = ans[ans.size() - 1] + ans[ans.size() - 2]; // Sum of last two scores
                ans.push_back(temp);
            }
            // Otherwise, it's a number, convert to int and add it to the vector
            else
            {
                ans.push_back(stoi(operations[i])); // Convert string to int and add to vector
            }
        };

        // Calculate the sum of all valid points
        int sum = 0;
        for (int i = 0; i < ans.size(); i++)
        {
            sum += ans[i];
        }

        return sum;
    }
};

int main()
{
    vector<string> operations = {"5", "2", "C", "D", "+"}; // Sample input

    Solution solution;

    // Calculate and print the total points
    int result = solution.calPoints(operations);
    cout << "Total Points: " << result << " ";
}

Example Walkthrough:

Let’s take an example to understand this:

Input: operations = ["5", "2", "C", "D", "+"]

First, we push 5 (score: [5]).
Then, we push 2 (score: [5, 2]).
"C" removes the last score, so we pop 2 (score: [5]).
"D" doubles the last score, so we add 10 (score: [5, 10]).
"+" sums the last two scores (5 + 10 = 15), so we add 15 (score: [5, 10, 15]).

Total Score: 5 + 10 + 15 = 30

In JAVA

import java.util.*;

class Solution {
    public int calPoints(String[] operations) {
        List<Integer> ans = new ArrayList<>(); // List to store valid points

        for (String operation : operations) {
            if (operation.equals("C")) {
                ans.remove(ans.size() - 1); // Remove last valid score
            } else if (operation.equals("D")) {
                int temp = 2 * ans.get(ans.size() - 1); // Double the last valid score
                ans.add(temp);
            } else if (operation.equals("+")) {
                int temp = ans.get(ans.size() - 1) + ans.get(ans.size() - 2); // Sum of last two valid scores
                ans.add(temp);
            } else {
                ans.add(Integer.parseInt(operation)); // Convert string to int and add to list
            }
        }

        // Calculate the total sum of valid points
        int sum = 0;
        for (int score : ans) {
            sum += score;
        }

        return sum;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] operations = {"5", "2", "C", "D", "+"}; // Sample input

        // Calculate and print the total points
        int result = solution.calPoints(operations);
        System.out.println("Total Points: " + result);
    }
}

Breakdown of the Java Code:

ArrayList for Storing Scores:
- We use an ArrayList<Integer> to store valid scores because it offers dynamic resizing, similar to a vector in C++.
Loop Through Operations:
- We use a for-each loop (for (String operation : operations)) to iterate through each operation.
- "C" triggers the removal of the last score by calling remove().
- "D" doubles the last valid score and adds it using add().
- "+" adds the last two scores by accessing them via get().
Final Sum:
- After all operations, we sum the scores in the list using a simple loop.

Adobe

Easy

LeetCode

easy