Baseball Game

Q: Wie unterscheidest du im Baseballspiel eine Zahl von einer Operation?

Vergleiche den Eintrag zuerst mit den drei Symbolen "+" , "D" und "C" und behandle alles andere als Ganzzahl. Die Konvertierung mit dem Parser der Sprache berücksichtigt ein vorangestelltes Minuszeichen, sodass "-30000" zu -30000 wird.

LeichtStack

+10

Du führst bei einem ungewöhnlichen Spiel Buch über die Punkte. Die Liste operations wird von links nach rechts gelesen, und jeder Eintrag ändert eine Aufzeichnung der Punkte. Eine Ganzzahl wie "7" oder "-2" fügt diese Punktzahl zur Aufzeichnung hinzu. "+" fügt eine Punktzahl hinzu, die der Summe der beiden neuesten Punktzahlen entspricht, "D" fügt eine Punktzahl hinzu, die dem Doppelten der neuesten Punktzahl entspricht, und "C" entfernt die neueste Punktzahl endgültig aus der Aufzeichnung.

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

Funktion

calPoints(operations: string-array) → integer

operationsstring-array: die Operationen der Reihe nach: Ganzzahlen als Text oder "+", "D", "C"
Gibt zurückinteger: die Summe der Punkte, die am Ende noch in der Aufzeichnung stehen

Einschränkungen

1 ≤ operations.length ≤ 5000
Jeder Eintrag ist "+", "D", "C" oder eine als Dezimalzahl geschriebene ganze Zahl mit -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Jede Operation ist gültig: "+" kommt nur dann vor, wenn der Datensatz mindestens zwei Punktzahlen enthält, "D" und "C" nur dann, wenn er mindestens eine enthält.
Jede Punktzahl im Datensatz 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, "+" fügt -2 + -4 = -6 hinzu, "C" entfernt dieses -6, und 7 kommt zuletzt hinzu. Die Summe des Datensatzes [4, -2, -4, 7] ist 5.

Eingabe: operations = ["6", "D", "C", "C"]
Ausgabe: 0
Erklärung: "D" fügt nach der 6 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 addieren 1 + 2 = 3 und dann 2 + 3 = 5, und "D" fügt 10 hinzu. Der Datensatz [1, 2, 3, 5, 10] ergibt in der Summe 21.

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du die Summe zurückgeben, ohne den Datensatz am Ende aufzusummieren, sodass jede Operation, einschließlich einer Stornierung, O(1) Zeit benötigt?

Tipps

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

0 von 3 geöffnet

Lösung

Jede Operation betrachtet die neuesten Punktzahlen, und mit "C" lassen sich Punktzahlen einzeln entfernen, sodass die Punktzahlen vor einer annullierten wieder die neuesten werden. Dieses Last-in-first-out-Muster entspricht genau einem Stack. Lege jede neue Punktzahl auf den Stack, entferne bei "C" das oberste Element und lies für "D" und "+" die obersten ein oder zwei Einträge aus.

Erstelle den Punktestand auf einem Stack und addiere ihn am Ende.

Idee

Führe die Ergebnisse als Liste, in der der neueste Punktestand am Ende steht. Dann betrifft jede Operation nur das Ende der Liste: Eine ganze Zahl wird hinzugefügt, "D" fügt das Doppelte des letzten Eintrags hinzu, "+" fügt die Summe der letzten beiden Einträge hinzu, und "C" entfernt den letzten Eintrag.

Warum ein Stack ausreicht: Nach einem "C" wird der zuvor zweitneueste Punktestand zum neuesten, und genau diesen muss eine folgende "D"- oder "+"-Operation lesen. Durch das Entfernen erhältst du ihn kostenlos. Im ersten Beispiel entfernt "C" -6 und lässt [4, -2, -4] übrig, sodass jedes spätere "+" erneut -2 + -4 addieren würde.

Wenn keine Operationen mehr übrig sind, enthält die Liste genau die Punktestände, die zählen. Addiere sie. Jede Operation benötigt O(1) und die abschließende Summe O(n), daher benötigt der gesamte Ablauf O(n) Zeit und für den Stack O(n) Speicherplatz.

Algorithmus

Beginne mit einem leeren Stapel record.
Bei "+" lege die Summe der beiden obersten Einträge auf den Stapel. Bei "D" lege das Doppelte des obersten Eintrags auf den Stapel.
Bei "C" entferne den obersten Eintrag vom Stapel.
Andernfalls ist der Eintrag eine Zahl: Wandle den Text in eine Ganzzahl um und lege sie auf den Stapel.
Gib die Summe aller auf dem Stapel verbliebenen Einträge 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

Die abschließende Schleife über den Stack ist zusätzliche Arbeit, die du vermeiden kannst. Behalte eine Variable total, die immer der Summe des Stacks entspricht. Jeder Push-Vorgang addiert die neue Punktzahl zu total, und jedes "C" zieht die Punktzahl ab, die es entfernt.

Der Stack wird weiterhin benötigt. Bei einer Stornierung muss bekannt sein, welche Punktzahl von der Gesamtsumme abgezogen werden soll, und "+" sowie "D" müssen nach jeder Stornierung die neuesten Punktzahlen kennen. Im ersten Beispiel verändert sich die Gesamtsumme zu 4, 2, -2, -8, dann nimmt die Stornierung die -6 wieder heraus, sodass -2 übrig bleibt, und die abschließende 7 bringt sie auf 5.

Die Laufzeit beträgt bei einem einzigen Durchlauf O(n), und die Antwort steht nach jedem Präfix der Vorgänge bereit, was wichtig ist, wenn Punktzahlen fortlaufend eintreffen. Der Speicherbedarf beträgt O(n): Alle n Vorgänge könnten Zahlen sein, die in der Aufzeichnung bleiben.

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

Die Regeln sind kurz, daher entstehen die meisten Fehler dadurch, dass der falsche Punktestand gelesen oder der Text falsch geparst wird.

Nur eine laufende Summe und die letzten beiden Punktestände zu behalten. Nach einem "C" brauchst du den Punktestand vor diesen beiden, daher liest ein Abbruch gefolgt von "+" veraltete Werte. Behalte den gesamten Stapel.
Zu vergessen, dass stornierte Punktestände aus der Summe herausgerechnet werden. Bei einer laufenden Summe muss "C" den entfernten Punktestand abziehen und darf ihn nicht ignorieren.
Negative Punktestände von Hand zu parsen und dabei das Vorzeichen zu verlieren. Verwende den Integer-Parser der Sprache, der "-2" als -2 liest.
Zu prüfen, ob ein Eintrag eine Ziffer enthält, um zu entscheiden, ob er eine Zahl ist. "-5" beginnt mit einem Minuszeichen; prüfe auf die drei Symbole und behandle alles andere als Zahl.
Davon auszugehen, dass die Antwort positiv ist. Negative Punktestände und Stornierungen können eine negative Summe ergeben oder 0, wenn alle Punktestände storniert wurden.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität des Baseballspiels?

Jede Operation erledigt eine konstante Menge an Arbeit auf dem Stack, daher dauert die Verarbeitung von n Operationen O(n) Zeit. Das Addieren des Stacks am Ende benötigt höchstens weitere O(n), und eine laufende Summe macht sogar das überflüssig. Der Stack benötigt O(n) Speicherplatz, wenn die meisten Operationen Punkte hinzufügen.

Warum ist ein Stack die richtige Datenstruktur für Baseball Game?

Jede Regel liest die zuletzt eingetragenen Punktzahlen oder entfernt sie, und durch ein Abbrechen wird die Punktzahl davor wieder sichtbar. Das ist die Last-in-first-out-Reihenfolge, die ein Stack mit O(1) für Push, Pop und Peek bietet. Ein einfaches Array oder eine Liste, die nur an ihrem Ende verwendet wird, funktioniert in jeder Sprache als Stack.

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

Nicht allgemein. Eine Folge von Zahlen, auf die eine Folge von "C"-Einträgen folgt, macht sie in umgekehrter Reihenfolge ungültig. Deshalb musst du dir jede Zahl merken, bis du weißt, ob sie ungültig gemacht wird. Im ungünstigsten Fall benötigt das O(n) Speicher. Eine laufende Summe spart den abschließenden Durchlauf, nicht aber den Stack.

Wie unterscheidest du im Baseballspiel eine Zahl von einer Operation?

Vergleiche den Eintrag zuerst mit den drei Symbolen "+", "D" und "C" und behandle alles andere als Ganzzahl. Die Konvertierung mit dem Parser der Sprache berücksichtigt ein vorangestelltes Minuszeichen, sodass "-30000" zu -30000 wird.

Python

def calPoints(operations):
    # Schreibe hier Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet