Baseball Game

Q: ¿Cómo distingues un número de una operación en Baseball Game?

Compara la entrada primero con los tres símbolos "+" , "D" y "C" , y trata cualquier otra cosa como un entero. La conversión con el analizador del lenguaje maneja un signo menos inicial, así que "-30000" se convierte en -30000 .

FácilPila

+10

Llevas la puntuación de un juego inusual. La lista operations se lee de izquierda a derecha, y cada entrada modifica un registro de puntuaciones. Un número entero como "7" o "-2" añade esa puntuación al registro. "+" añade una puntuación igual a la suma de las dos puntuaciones más recientes, "D" añade una puntuación igual al doble de la puntuación más reciente y "C" elimina definitivamente del registro la puntuación más reciente.

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: números enteros como texto, o "+", "D", "C"
Devuelveinteger: la suma de las puntuaciones que aún figuran en el registro al final

Restricciones

1 ≤ operations.length ≤ 5000
Cada entrada es "+", "D", "C" o un entero escrito en decimal con -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Cada operación es válida: "+" aparece solo cuando el registro contiene al menos dos puntuaciones, "D" y "C" 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 se añade al final. El registro [4, -2, -4, 7] suma 5.

Entrada: operations = ["6", "D", "C", "C"]
Salida: 0
Explicación: "D" añade 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.

+13 pruebas ocultas al enviar

Para ir más allá

¿Puedes devolver la suma sin sumar el registro del final, para que cada operación, incluida una cancelación, tome O(1) de tiempo?

Pistas

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

0 de 3 abiertas

Solución

Cada operación tiene en cuenta las puntuaciones más recientes, y "C" puede quitar las puntuaciones de una en una, así que las puntuaciones anteriores a una cancelada vuelven a ser las más recientes. Ese patrón de último en entrar, primero en salir es exactamente una pila. Apila cada puntuación nueva, desapila con "C" y consulta la última o las dos últimas entradas para "D" y "+".

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

Intuición

Mantén el registro como una lista en la que la puntuación más reciente esté al final. Después, cada operación solo afecta al final de la lista: se añade un entero, "D" añade el doble de la última entrada, "+" añade la suma de las dos últimas entradas y "C" elimina la última entrada.

Por qué basta con una pila: después de un "C", la puntuación que era la penúltima pasa a ser la más reciente, y esa es la que debe leer un "D" o un "+" posterior. Al eliminar la última entrada, obtienes eso directamente. En el primer ejemplo, "C" elimina -6 y deja [4, -2, -4], así que cualquier "+" posterior volvería a sumar -2 + -4.

Cuando se agotan las operaciones, la lista contiene exactamente las puntuaciones que cuentan. Súmalas. Cada operación es O(1) y la suma final es O(n), por lo que todo el proceso tarda O(n) y requiere O(n) de espacio para la pila.

Algoritmo

Empieza con una pila vacía record.
Para "+", apila la suma de las dos entradas superiores. Para "D", apila el doble de la entrada superior.
Para "C", desapila la entrada superior.
De lo contrario, la entrada es un número: convierte el texto en un entero y apílalo.
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

El bucle final que recorre la pila es trabajo extra que puedes evitar. Mantén una variable total que siempre sea igual a la suma de la pila. Cada inserción añade la nueva puntuación a total, y cada "C" resta la puntuación que extrae.

La pila sigue siendo necesaria. Una cancelación debe saber qué puntuación quitar del total, y "+" y "D" deben conocer las puntuaciones más recientes después de cualquier cancelación. En el primer ejemplo, el total pasa por 4, 2, -2, -8; después, la cancelación vuelve a añadir -6 para obtener -2, y el 7 final lo lleva a 5.

El tiempo es O(n) con un solo recorrido, y la respuesta está lista después de cualquier prefijo de las operaciones, lo cual importa cuando las puntuaciones llegan en tiempo real. El espacio es O(n): las n operaciones podrían ser números que permanezcan en el registro.

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 mismo.
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

Las reglas son breves, así que la mayoría de los errores se deben a leer la puntuación equivocada o a analizar el texto incorrectamente.

Conservar solo un total acumulado y las dos últimas puntuaciones. Después de un "C", necesitas la puntuación anterior a esas dos, así que una cancelación seguida de "+" lee valores obsoletos. Conserva toda la pila.
Olvidar que las puntuaciones canceladas se restan del total. Si llevas un total acumulado, "C" debe restar la puntuación extraída, no ignorarla.
Analizar manualmente las puntuaciones negativas y omitir el signo. Usa el analizador de enteros del lenguaje, que lee "-2" como -2.
Comprobar si hay un dígito para decidir si una entrada es un número. "-5" empieza con un signo menos; comprueba los tres símbolos y trata todo lo demás como un número.
Suponer que la respuesta es positiva. Las puntuaciones negativas y las cancelaciones pueden dar como resultado una suma negativa, o 0 si se cancelaron todas las puntuaciones.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Baseball Game?

Cada operación realiza una cantidad constante de trabajo en la parte superior de la pila, así que procesar n operaciones toma un tiempo O(n). Sumar la pila al final requiere como máximo otro O(n), y un total acumulado elimina incluso eso. La pila usa espacio O(n) cuando la mayoría de las operaciones añaden puntuaciones.

¿Por qué una pila es la estructura de datos adecuada para Baseball Game?

Cada regla lee o elimina las puntuaciones más recientes, y una cancelación deja al descubierto la puntuación anterior. Ese es el orden de último en entrar, primero en salir, que es lo que te ofrece una pila con operaciones de inserción, extracción y consulta del elemento superior en O(1). Un arreglo o una lista simples que se usan solo por el extremo sirven como pila en cualquier lenguaje.

¿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. Un total acumulado evita el recorrido final, no la pila.

¿Cómo distingues un número de una operación en Baseball Game?

Compara la entrada primero con los tres símbolos "+", "D" y "C", y trata cualquier otra cosa como un entero. La conversión con el analizador del lenguaje maneja un signo menos inicial, así que "-30000" se convierte en -30000.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado