Baseball Game

+10

Tieni il punteggio di un gioco insolito. Leggi operations da sinistra a destra; ogni voce modifica un registro dei punteggi. Un numero intero come "7" o "-2" aggiunge quel punteggio. "+" aggiunge la somma degli ultimi due punteggi, "D" aggiunge il doppio dell’ultimo punteggio e "C" rimuove definitivamente l’ultimo punteggio.

Scrivi una funzione chiamata calPoints che restituisca la somma dei punteggi rimasti nel registro dopo l’ultima operazione. Un registro vuoto ha somma 0.

Funzione

calPoints(operations: string-array) → integer

operationsstring-array: le operazioni in ordine: interi come testo, oppure "+", "D", "C"
Restituisceinteger: la somma dei punteggi ancora presenti nel record alla fine

Vincoli

1 ≤ operations.length ≤ 5000
Ogni elemento è "+", "D", "C" oppure un intero scritto in notazione decimale con -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Ogni operazione è valida: "+" compare solo quando il record contiene almeno due punteggi, "D" e "C" solo quando ne contiene almeno uno.
Ogni punteggio nel record e la somma finale rientrano in un intero con segno a 32 bit.

Esempi

Input: operations = ["4", "-2", "D", "+", "C", "7"]
Output: 5
Spiegazione: Il registro cresce fino a [4, -2], "D" aggiunge -4, "+" aggiunge -2 + -4 = -6, "C" rimuove quel -6 e 7 viene aggiunto per ultimo. Il registro [4, -2, -4, 7] dà come somma 5.

Input: operations = ["6", "D", "C", "C"]
Output: 0
Spiegazione: "D" aggiunge 12 dopo il 6, poi le due voci "C" rimuovono 12 e 6. Non resta nulla, quindi la risposta è 0.

Input: operations = ["1", "2", "+", "+", "D"]
Output: 21
Spiegazione: Le due voci "+" sommano 1 + 2 = 3 e poi 2 + 3 = 5, e "D" aggiunge 10. Il record [1, 2, 3, 5, 10] dà come somma 21.

Per approfondire

Come aggiungeresti un'operazione che annulla l'ultimo "C", ripristinando il punteggio cancellato, in tempo O(1)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni operazione legge i punteggi più recenti e "C" può rimuoverli uno alla volta, così i punteggi più vecchi diventano di nuovo i più recenti. È un sistema ultimo a entrare, primo a uscire: inserisci ogni nuovo punteggio, rimuovilo con "C" e leggi quello in cima o i due in cima per "D" e "+".

Costruisci il record su uno stack e sommalo alla fine

Intuizione

Conserva il registro come una lista con il punteggio più recente alla fine, così ogni operazione agisce solo sulla fine. Dopo un "C", il secondo punteggio più recente diventa il più recente, e un successivo "D" o "+" deve leggerlo; rimuovendo l’ultimo elemento, lo si rende accessibile. Nel primo esempio, "C" rimuove -6 e lascia [4, -2, -4].

Quando le operazioni finiscono, la lista contiene esattamente i punteggi che contano, quindi sommali: tempo O(n) e spazio O(n).

Algoritmo

Inizia con uno stack vuoto record.
Per "+", inserisci la somma delle due voci in cima. Per "D", inserisci il doppio della voce in cima.
Per "C", rimuovi la voce in cima.
Altrimenti, la voce è un numero: converti il testo in un intero e inseriscilo.
Restituisci la somma di tutto ciò che rimane nello stack.

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)

Stack con un totale progressivo

Intuizione

Mantieni total uguale alla somma della pila: ogni inserimento aggiunge il nuovo punteggio e ogni "C" sottrae il punteggio che rimuove. La pila deve rimanere, perché un annullamento deve sapere quale punteggio togliere. Nel primo esempio il totale passa per 4, 2, -2, -8, l'annullamento rimuove -6, riportandolo a -2, e 7 lo porta a 5.

Si tratta di un'unica passata con tempo O(n), e la risposta è pronta dopo qualsiasi prefisso delle operazioni. Lo spazio è O(n), poiché ogni operazione potrebbe essere un numero che rimane.

Algoritmo

Inizia con uno stack vuoto record e total = 0.
Per "C", rimuovi il punteggio in cima e sottrai da total.
Altrimenti calcola il nuovo punteggio: la somma dei due punteggi in cima per "+", il doppio del punteggio in cima per "D" oppure il numero intero stesso.
Inserisci il nuovo punteggio nello stack e aggiungilo a total.
Restituisci 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

Trappole e casi limite

Mantenere solo un totale progressivo e gli ultimi due punteggi. In ["1", "2", "3", "C", "+"] "+" ha bisogno di 1 e 2, ma una finestra di due punteggi ha già perso 1.
Non sottrarre dal totale progressivo un punteggio annullato. Nel secondo esempio, il risultato è 18 invece di 0.
Decidere che una voce è un numero controllando se contiene una cifra. "-2" inizia con un segno meno; confrontala con i tre simboli e analizza tutto il resto con il parser di interi del linguaggio.
Supporre che la risposta sia positiva. ["-3", "D"] dà come somma -9.

Domande frequenti3

Qual è la complessità temporale del Baseball Game?

Ogni operazione richiede un tempo costante sulla cima dello stack, quindi n operazioni richiedono un tempo O(n). Lo stack occupa O(n) spazio quando la maggior parte delle operazioni aggiunge punteggi.

Perché uno stack è la struttura dati giusta per Baseball Game?

Ogni regola legge o rimuove i punteggi più recenti e un annullamento rende visibile il punteggio precedente. Questo è un comportamento LIFO (ultimo a entrare, primo a uscire), che uno stack offre con push, pop e peek in O(1). Un array usato solo dalla sua estremità funziona come uno stack.

È possibile risolvere Baseball Game usando O(1) spazio aggiuntivo?

Non in generale. Una sequenza di numeri seguita da una sequenza di voci "C" le annulla in ordine inverso, quindi devi ricordare ogni numero finché non sai se verrà annullato. Nel caso peggiore, ciò richiede O(n) di memoria.

def calPoints(operations):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso