Baseball Game

Q: Come si distingue un numero da un'operazione in Baseball Game?

Confronta prima la voce con i tre simboli "+" , "D" e "C" , e considera qualsiasi altra cosa un intero. La conversione tramite il parser del linguaggio gestisce il segno meno iniziale, quindi "-30000" diventa -30000 .

FacileStack

+10

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

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

Funzione

calPoints(operations: string-array) → integer

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

Vincoli

1 ≤ operations.length ≤ 5000
Ogni voce è "+", "D", "C" oppure un intero scritto in notazione decimale con -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Ogni operazione è valida: "+" si verifica solo quando il registro 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 record cresce fino a [4, -2], "D" aggiunge -4, "+" aggiunge -2 + -4 = -6, "C" rimuove quel -6 e infine viene aggiunto 7. Il record [4, -2, -4, 7] ha 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 rimane 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, mentre "D" aggiunge 10. Il record [1, 2, 3, 5, 10] dà come somma 21.

+13 test nascosti all’invio

Per approfondire

Riesci a restituire la somma senza sommare il record alla fine, in modo che ogni operazione, inclusa una cancellazione, richieda O(1) tempo?

Suggerimenti

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

0 di 3 aperti

Soluzione

Ogni operazione esamina i punteggi più recenti e "C" può rimuovere i punteggi uno alla volta, così quelli precedenti a un punteggio annullato tornano a essere i più recenti. Questo schema LIFO (ultimo a entrare, primo a uscire) è esattamente uno stack. Inserisci ogni nuovo punteggio, rimuovi l’ultimo con "C" e leggi una o due voci in cima per "D" e "+".

Costruisci il record su una pila, sommalo alla fine

Intuizione

Conserva i punteggi in una lista, con il punteggio più recente alla fine. Così ogni operazione agisce solo sulla fine della lista: si aggiunge un intero, "D" aggiunge il doppio dell’ultimo elemento, "+" aggiunge la somma degli ultimi due elementi e "C" rimuove l’ultimo elemento.

Perché basta uno stack: dopo un "C", il punteggio che era il penultimo diventa il più recente, ed è quello che la successiva operazione "D" o "+" deve leggere. Rimuovendolo, lo ottieni automaticamente. Nel primo esempio, "C" rimuove -6 e lascia [4, -2, -4], quindi un eventuale "+" successivo sommerebbe di nuovo -2 + -4.

Quando le operazioni finiscono, la lista contiene esattamente i punteggi validi. Somma i valori. Ogni operazione è O(1) e la somma finale è O(n), quindi l’esecuzione completa richiede un tempo O(n) e uno spazio O(n) per lo stack.

Algoritmo

Inizia con uno stack vuoto record.
Per "+", inserisci la somma dei due valori in cima. Per "D", inserisci il doppio del valore in cima.
Per "C", rimuovi il valore in cima.
Altrimenti, il valore è un numero: converti il testo in un intero e inseriscilo.
Restituisci la somma di tutti i valori rimasti 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

Il ciclo finale sulla pila è lavoro extra che puoi evitare. Mantieni una variabile total che sia sempre uguale alla somma della pila. Ogni inserimento aggiunge il nuovo punteggio a total e ogni "C" sottrae il punteggio che estrae.

La pila è comunque necessaria. Un annullamento deve sapere quale punteggio sottrarre dal totale, mentre "+" e "D" devono conoscere gli ultimi punteggi dopo gli eventuali annullamenti. Nel primo esempio il totale passa per 4, 2, -2, -8, poi l'annullamento sottrae -6, portandolo a -2, e il 7 finale lo porta a 5.

Il tempo è O(n) con un'unica scansione, e la risposta è pronta dopo qualsiasi prefisso delle operazioni, il che è importante quando i punteggi arrivano in tempo reale. Lo spazio è O(n): tutte le n operazioni potrebbero essere numeri che rimangono nel registro.

Algoritmo

Inizia con uno stack vuoto record e total = 0.
Per "C", rimuovi il punteggio in cima e sottrailo 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

Le regole sono brevi, quindi la maggior parte dei bug deriva dalla lettura del punteggio sbagliato o dall'analisi del testo.

Conservare solo un totale progressivo e gli ultimi due punteggi. Dopo un "C", ti serve il punteggio precedente a quei due, quindi un annullamento seguito da "+" usa valori non aggiornati. Conserva l'intero stack.
Dimenticare che i punteggi annullati vengono sottratti dal totale. Con un totale progressivo, "C" deve sottrarre il punteggio estratto, non ignorarlo.
Analizzare a mano i punteggi negativi e perdere il segno. Usa il parser di interi del linguaggio, che legge "-2" come -2.
Controllare se c'è una cifra per decidere se una voce è un numero. "-5" inizia con un segno meno; verifica i tre simboli e tratta tutto il resto come un numero.
Supporre che la risposta sia positiva. I punteggi negativi e gli annullamenti possono lasciare una somma negativa, oppure 0 se tutti i punteggi sono stati annullati.

Domande frequenti4

Qual è la complessità temporale di Baseball Game?

Ogni operazione esegue una quantità costante di lavoro in cima allo stack, quindi elaborare n operazioni richiede un tempo O(n). Sommare i valori dello stack alla fine richiede al massimo un altro O(n), e un totale progressivo elimina anche questo passaggio. Lo stack usa 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 rivela il punteggio precedente. Questo è un ordine last-in, first-out, che è ciò che ti offre uno stack con operazioni di push, pop e peek in O(1). Un semplice array o una lista usati solo alla fine funzionano da stack in qualsiasi linguaggio.

È 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, questo richiede memoria O(n). Un totale progressivo evita il passaggio finale, non lo stack.

Come si distingue un numero da un'operazione in Baseball Game?

Confronta prima la voce con i tre simboli "+", "D" e "C", e considera qualsiasi altra cosa un intero. La conversione tramite il parser del linguaggio gestisce il segno meno iniziale, quindi "-30000" diventa -30000.

Python

def calPoints(operations):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso