Baseball Game

+10

Du führst bei einem ungewöhnlichen Spiel Buch über die Punkte. Lies operations von links nach rechts; jeder Eintrag verändert die Liste der Punkte. Eine ganze Zahl wie "7" oder "-2" fügt diese Punktzahl hinzu. "+" fügt die Summe der beiden neuesten Punktzahlen hinzu, "D" fügt das Doppelte der neuesten Punktzahl hinzu und "C" entfernt die neueste Punktzahl endgültig.

Schreibe eine Funktion namens calPoints, die die Summe der Punktzahlen zurückgibt, die nach der letzten Operation in der Liste verbleiben. Eine leere Liste ergibt 0.

Funktion

calPoints(operations: string-array) → integer

operationsstring-array: die Operationen der Reihe nach: ganze Zahlen als Text oder "+", "D", "C"
Gibt zurückinteger: die Summe der Punkte, die am Ende noch auf der Liste stehen

Einschränkungen

1 ≤ operations.length ≤ 5000
Jeder Eintrag ist "+", "D", "C" oder eine ganze Zahl, die dezimal geschrieben ist, wobei -3 × 10⁴ ≤ value ≤ 3 × 10⁴ gilt.
Jede Operation ist gültig: "+" kommt nur vor, wenn der Datensatz mindestens zwei Punktzahlen enthält, "D" und "C" nur, wenn er mindestens eine enthält.
Jeder Punktestand in der Aufzeichnung und die Endsumme passen in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: operations = ["4", "-2", "D", "+", "C", "7"]
Ausgabe: 5
Erklärung: Der Datensatz wächst auf [4, -2], "D" fügt -4 hinzu, "+" addiert -2 + -4 = -6, "C" entfernt diese -6, und 7 kommt zuletzt hinzu. Die Summe des Datensatzes [4, -2, -4, 7] beträgt 5.

Eingabe: operations = ["6", "D", "C", "C"]
Ausgabe: 0
Erklärung: "D" fügt nach der 6 eine 12 hinzu, dann entfernen die beiden "C"-Einträge 12 und 6. Es bleibt nichts übrig, also ist die Antwort 0.

Eingabe: operations = ["1", "2", "+", "+", "D"]
Ausgabe: 21
Erklärung: Die beiden "+"-Einträge ergeben 1 + 2 = 3 und dann 2 + 3 = 5, und "D" addiert 10. Der Datensatz [1, 2, 3, 5, 10] ergibt in der Summe 21.

Weiterführende Frage

Wie würdest du eine Operation hinzufügen, die das zuletzt ausgeführte "C" rückgängig macht und den gestrichenen Punktestand zurücksetzt, und zwar in O(1)-Zeit?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jede Operation liest die neuesten Punktzahlen, und "C" kann sie einzeln entfernen, sodass ältere Punktzahlen wieder zu den neuesten werden. Das ist Last In, First Out: Füge jede neue Punktzahl hinzu, entferne bei "C" die oberste und lies die oberste oder die obersten zwei für "D" und "+".

Erstelle den Spielstand auf einem Stapel und addiere ihn am Ende zusammen

Idee

Führe den Verlauf als Liste, wobei der neueste Punktestand am Ende steht, damit jede Operation nur das Ende betrifft. Nach einem "C" wird der zweitneueste Punktestand zum neuesten, und ein späteres "D" oder "+" muss ihn auslesen; durch das Entfernen wird er sichtbar. Im ersten Beispiel entfernt "C" -6 und lässt [4, -2, -4] übrig.

Wenn keine Operationen mehr anstehen, enthält die Liste genau die Punktestände, die zählen. Addiere sie also: Zeitaufwand O(n) und Speicherplatz O(n).

Algorithmus

Beginne mit einem leeren Stapel record.
Bei "+" wird die Summe der obersten beiden Einträge auf den Stapel gelegt. Bei "D" wird das Doppelte des obersten Eintrags auf den Stapel gelegt.
Bei "C" wird der oberste Eintrag vom Stapel entfernt.
Andernfalls ist der Eintrag eine Zahl: Wandle den Text in eine Ganzzahl um und lege sie auf den Stapel.
Gib die Summe aller verbleibenden Einträge auf dem Stapel zurück.

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)

Stapel mit laufender Summe

Idee

Halte total gleich der Summe des Stacks: Jeder Push-Vorgang addiert den neuen Punktestand, und jedes "C" zieht den Punktestand ab, den es entfernt. Der Stack muss erhalten bleiben, denn bei einem Abbrechen muss bekannt sein, welcher Punktestand entfernt werden soll. Im ersten Beispiel verändert sich die Gesamtsumme zu 4, 2, -2, -8; durch das Abbrechen wird -6 wieder hinzugefügt, sodass -2 herauskommt, und 7 bringt die Summe auf 5.

Das ist ein Durchlauf mit einer Laufzeit von O(n), und die Antwort steht nach jedem Präfix der Operationen fest. Der Speicherbedarf beträgt O(n), da jede Operation eine Zahl sein könnte, die im Stack bleibt.

Algorithmus

Beginne mit einem leeren Stapel record und total = 0.
Bei "C" entfernst du den obersten Punktestand und ziehst ihn von total ab.
Berechne andernfalls den neuen Punktestand: die Summe der beiden obersten bei "+", das Doppelte des obersten bei "D" oder die ganze Zahl selbst.
Lege den neuen Punktestand auf den Stapel und addiere ihn zu total.
Gib total zurück.

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

Stolperfallen und Grenzfälle

Nur eine laufende Summe und die letzten beiden Punktzahlen behalten. In ["1", "2", "3", "C", "+"] benötigt "+" die Werte 1 und 2, und in einem Fenster mit zwei Punktzahlen ist die 1 bereits verloren gegangen.
Eine gestrichene Punktzahl nicht von der laufenden Summe abziehen. Im zweiten Beispiel ergibt das 18 statt 0.
Entscheiden, dass ein Eintrag eine Zahl ist, indem geprüft wird, ob er eine Ziffer enthält. "-2" beginnt mit einem Minuszeichen; vergleiche den Eintrag mit den drei Symbolen und wandle alles andere mit dem Ganzzahl-Parser der Sprache um.
Annehmen, dass die Antwort positiv ist. ["-3", "D"] ergibt die Summe -9.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des Baseballspiels?

Jede Operation führt eine konstante Arbeit auf dem obersten Element des Stapels aus, daher benötigen n Operationen O(n) Zeit. Der Stapel benötigt O(n) Speicherplatz, wenn die meisten Operationen Punktzahlen hinzufügen.

Warum ist ein Stack die richtige Datenstruktur für das Baseballspiel?

Jede Regel liest die zuletzt erzielten Punktzahlen oder entfernt sie, und durch ein Abbrechen wird die Punktzahl davor wieder sichtbar. Das ist „Zuletzt rein, zuerst raus“ – eine Eigenschaft, die ein Stack mit O(1) für Push, Pop und Peek bietet. Ein Array, das nur an seinem Ende verwendet wird, funktioniert als Stack.

Kann Baseball Game mit O(1) zusätzlichem Speicherplatz gelöst werden?

Nicht grundsätzlich. Auf eine Zahlenfolge folgt eine Folge von "C"-Einträgen, die die Zahlen in umgekehrter Reihenfolge aufhebt. Daher musst du dir jede Zahl merken, bis du weißt, ob sie aufgehoben wird. Im schlimmsten Fall benötigt das O(n) Speicher.

def calPoints(operations):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe