Baseball Game

FácilPila

+10

Llevas la puntuación de un juego poco común. Lee operations de izquierda a derecha; cada entrada modifica el registro de puntuaciones. Un número entero como "7" o "-2" añade esa puntuación. "+" añade la suma de las dos últimas puntuaciones, "D" añade el doble de la última puntuación y "C" elimina definitivamente la última puntuación.

Escribe una función llamada calPoints que devuelva la suma de las puntuaciones que quedan en el registro después de la última operación. Un registro vacío suma 0.

Función

calPoints(operations: string-array) → integer

operationsstring-array: las operaciones en orden: enteros como texto, o "+", "D", "C"
Devuelveinteger: la suma de las puntuaciones que aún están registradas al final

Restricciones

1 ≤ operations.length ≤ 5000
Cada entrada es "+", "D", "C" o un número entero escrito en decimal con -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Todas las operaciones son válidas: "+" aparece solo cuando el registro contiene al menos dos puntuaciones; "D" y "C" aparecen solo cuando contiene al menos una.
Cada puntuación del registro y la suma final caben en un entero con signo de 32 bits.

Ejemplos

Entrada: operations = ["4", "-2", "D", "+", "C", "7"]
Salida: 5
Explicación: El registro crece hasta [4, -2], "D" añade -4, "+" añade -2 + -4 = -6, "C" elimina ese -6 y 7 va al final. El registro [4, -2, -4, 7] suma 5.

Entrada: operations = ["6", "D", "C", "C"]
Salida: 0
Explicación: "D" agrega 12 después del 6, luego las dos entradas "C" eliminan 12 y 6. No queda nada, así que la respuesta es 0.

Entrada: operations = ["1", "2", "+", "+", "D"]
Salida: 21
Explicación: Las dos entradas "+" suman 1 + 2 = 3 y después 2 + 3 = 5, y "D" suma 10. El registro [1, 2, 3, 5, 10] suma 21.

Para ir más allá

¿Cómo añadirías una operación que deshaga el "C" más reciente y restablezca la puntuación cancelada en tiempo O(1)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada operación lee las puntuaciones más recientes, y "C" puede quitarlas de una en una, así que las puntuaciones más antiguas vuelven a ser las más recientes. Eso es último en entrar, primero en salir: añade cada puntuación nueva, extrae una con "C" y lee la última o las dos últimas para "D" y "+".

Construye el registro en una pila y súmalo al final

Intuición

Mantén el registro como una lista con la puntuación más reciente al final, de modo que cada operación solo afecte al final. Después de un "C", la segunda puntuación más reciente pasa a ser la más reciente, y un "D" o "+" posterior debe leerla; al quitar la última, queda expuesta. En el primer ejemplo, "C" quita -6 y deja [4, -2, -4].

Cuando se agotan las operaciones, la lista contiene exactamente las puntuaciones que cuentan, así que súmalas: tiempo O(n) y espacio O(n).

Algoritmo

Empieza con una pila vacía record.
Para "+", inserta la suma de las dos entradas superiores. Para "D", inserta el doble de la entrada superior.
Para "C", extrae la entrada superior.
De lo contrario, la entrada es un número: convierte el texto en un entero e insértalo.
Devuelve la suma de todo lo que queda en la pila.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    for op in operations:
        if op == "+":
            record.append(record[-1] + record[-2])
        elif op == "D":
            record.append(2 * record[-1])
        elif op == "C":
            record.pop()
        else:
            record.append(int(op))
    return sum(record)

Pila con un total acumulado

Intuición

Mantén total igual a la suma de la pila: cada inserción añade la nueva puntuación y cada "C" resta la puntuación que extrae. La pila debe mantenerse, porque una cancelación necesita saber qué puntuación quitar. En el primer ejemplo, el total pasa por 4, 2, -2, -8; la cancelación vuelve a sumar -6, dejándolo en -2, y 7 lo lleva a 5.

Esto es una sola pasada en tiempo O(n), y la respuesta está lista después de cualquier prefijo de las operaciones. El espacio es O(n), ya que cada operación podría ser un número que permanece.

Algoritmo

Empieza con una pila vacía record y total = 0.
Para "C", extrae la puntuación superior y réstala de total.
De lo contrario, calcula la nueva puntuación: la suma de las dos puntuaciones superiores para "+", el doble de la puntuación superior para "D" o el entero en sí.
Apila la nueva puntuación y súmala a total.
Devuelve total.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    total = 0    # always the sum of record
    for op in operations:
        if op == "C":
            total -= record.pop()  # the cancelled score leaves the total too
            continue
        if op == "+":
            score = record[-1] + record[-2]
        elif op == "D":
            score = 2 * record[-1]
        else:
            score = int(op)
        record.append(score)
        total += score
    return total

Errores comunes y casos límite

Conservar solo un total acumulado y las dos últimas puntuaciones. En ["1", "2", "3", "C", "+"], "+" necesita 1 y 2, y una ventana de dos puntuaciones ya ha perdido el 1.
No restar del total acumulado una puntuación cancelada. En el segundo ejemplo, eso deja 18 en lugar de 0.
Decidir que una entrada es un número comprobando si contiene un dígito. "-2" empieza con un signo menos; compara con los tres símbolos y analiza todo lo demás con el analizador de enteros del lenguaje.
Suponer que la respuesta es positiva. ["-3", "D"] suma -9.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del juego de béisbol?

Cada operación realiza un trabajo constante en la parte superior de la pila, por lo que n operaciones tardan O(n) tiempo. La pila ocupa O(n) espacio cuando la mayoría de las operaciones añaden puntuaciones.

¿Por qué una pila es la estructura de datos adecuada para el juego de béisbol?

Cada regla lee o elimina las puntuaciones más recientes, y una cancelación deja al descubierto la puntuación anterior. Eso es último en entrar, primero en salir, algo que una pila te ofrece con O(1) para insertar, extraer y consultar el elemento superior. Un array que se usa solo por su extremo funciona como una pila.

¿Se puede resolver Baseball Game con espacio extra O(1)?

No en general. Una secuencia de números seguida de una secuencia de entradas "C" las cancela en orden inverso, así que debes recordar cada número hasta saber si se cancelará. Eso requiere memoria O(n) en el peor de los casos.

def calPoints(operations):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

operations = ["4", "-2", "D", "+", "C", "7"]

Salida Esperada