Baseball Game

Q: Czy grę w baseball można rozwiązać przy użyciu O(1) dodatkowej przestrzeni?

Nie zawsze. Ciąg liczb, po którym następuje ciąg wpisów "C" , anuluje je w odwrotnej kolejności, więc musisz zapamiętać każdą liczbę, dopóki nie dowiesz się, czy zostanie anulowana. W najgorszym przypadku wymaga to pamięci O(n) .

ŁatweStos

+10

Prowadzisz punktację w nietypowej grze. Czytaj operations od lewej do prawej; każdy wpis zmienia zapis wyników. Liczba całkowita, taka jak "7" lub "-2", dodaje ten wynik. "+" dodaje sumę dwóch ostatnich wyników, "D" dodaje dwukrotność ostatniego wyniku, a "C" trwale usuwa ostatni wynik.

Napisz funkcję o nazwie calPoints, która zwraca sumę wyników pozostałych w zapisie po ostatniej operacji. Suma pustego zapisu wynosi 0.

Funkcja

calPoints(operations: string-array) → integer

operationsstring-array: operacje w kolejności: liczby całkowite zapisane jako tekst lub „+”, „D”, „C”
Zwracainteger: suma punktów nadal zapisanych w rejestrze na koniec

Ograniczenia

1 ≤ operations.length ≤ 5000
Każdy wpis to "+", "D", "C" albo liczba całkowita zapisana w systemie dziesiętnym, dla której -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Każda operacja jest prawidłowa: "+" pojawia się tylko wtedy, gdy rekord zawiera co najmniej dwa wyniki, a "D" i "C" tylko wtedy, gdy zawiera co najmniej jeden.
Każdy wynik w zapisie oraz suma końcowa mieszczą się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: operations = ["4", "-2", "D", "+", "C", "7"]
Wyjście: 5
Wyjaśnienie: Lista powiększa się do [4, -2], "D" dodaje -4, "+" dodaje -2 + -4 = -6, "C" usuwa tę wartość -6, a na końcu trafia 7. Suma listy [4, -2, -4, 7] wynosi 5.

Wejście: operations = ["6", "D", "C", "C"]
Wyjście: 0
Wyjaśnienie: "D" dodaje 12 po 6, a następnie dwa wpisy "C" usuwają 12 i 6. Nic nie zostaje, więc odpowiedź to 0.

Wejście: operations = ["1", "2", "+", "+", "D"]
Wyjście: 21
Wyjaśnienie: Dwa wpisy "+" dodają 1 + 2 = 3, a następnie 2 + 3 = 5, a "D" dodaje 10. Rekord [1, 2, 3, 5, 10] daje w sumie 21.

Pytanie dodatkowe

Jak dodać operację, która cofa ostatnie "C" i przywraca anulowany wynik w czasie O(1)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Każda operacja odczytuje najnowsze wyniki, a "C" może zdejmować je pojedynczo, dzięki czemu starsze wyniki znów stają się najnowsze. To zasada „ostatnie weszło, pierwsze wyszło”: dodawaj każdy nowy wynik, zdejmuj go przy "C" i odczytuj jeden lub dwa wyniki ze szczytu dla "D" i "+".

Buduj rekord na stosie, a na końcu go zsumuj

Intuicja

Przechowuj wyniki w postaci listy, z najnowszym wynikiem na końcu, tak aby każda operacja dotyczyła tylko końca listy. Po "C" drugi najnowszy wynik staje się najnowszym, a późniejsze "D" lub "+" muszą go odczytać; usunięcie ostatniego elementu go odsłania. W pierwszym przykładzie "C" usuwa -6 i pozostawia [4, -2, -4].

Gdy zabraknie operacji, lista zawiera dokładnie te wyniki, które się liczą, więc dodaj je do siebie: czas O(n) i pamięć O(n).

Algorytm

Zacznij od pustego stosu record.
Dla "+" dodaj do stosu sumę dwóch górnych wpisów. Dla "D" dodaj do stosu dwukrotność górnego wpisu.
Dla "C" zdejmij górny wpis ze stosu.
W przeciwnym razie wpis jest liczbą: przekonwertuj tekst na liczbę całkowitą i dodaj ją do stosu.
Zwróć sumę wszystkich wpisów pozostałych na stosie.

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)

Stos z sumą bieżącą

Intuicja

Utrzymuj total równe sumie elementów stosu: każde dodanie umieszcza nowy wynik na stosie, a każde "C" odejmuje wynik, który usuwa ze stosu. Stos musi pozostać, ponieważ anulowanie musi wiedzieć, który wynik usunąć. W pierwszym przykładzie suma zmienia się kolejno na 4, 2, -2, -8, anulowanie usuwa -6, co daje -2, a 7 podnosi sumę do 5.

To jedno przejście w czasie O(n), a odpowiedź jest gotowa po każdym prefiksie operacji. Złożoność pamięciowa wynosi O(n), ponieważ każda operacja może być liczbą, która pozostaje na stosie.

Algorytm

Zacznij od pustego stosu record i total = 0.
Dla "C" zdejmij wynik ze szczytu stosu i odejmij go od total.
W przeciwnym razie oblicz nowy wynik: sumę dwóch wyników ze szczytu dla "+", dwukrotność wyniku ze szczytu dla "D" albo samą liczbę całkowitą.
Umieść nowy wynik na stosie i dodaj go do total.
Zwróć 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

Pułapki i przypadki brzegowe

Przechowywanie tylko sumy bieżącej i dwóch ostatnich wyników. W ["1", "2", "3", "C", "+"] do obliczenia "+" potrzebne są 1 i 2, a okno dwóch wyników nie zawiera już 1.
Nieodejmowanie anulowanego wyniku od sumy bieżącej. W drugim przykładzie pozostaje wtedy 18 zamiast 0.
Uznawanie wpisu za liczbę na podstawie obecności cyfry. "-2" zaczyna się od znaku minus; porównaj wpis z trzema symbolami, a wszystko inne przetwórz za pomocą parsera liczb całkowitych danego języka.
Zakładanie, że wynik jest dodatni. Suma ["-3", "D"] wynosi -9.

Najczęstsze pytania3

Jaka jest złożoność czasowa gry w baseball?

Każda operacja wykonuje stałą pracę na wierzchołku stosu, więc n operacji zajmuje czas O(n). Stos zajmuje O(n) miejsca, gdy większość operacji dodaje wyniki.

Dlaczego stos jest odpowiednią strukturą danych w grze w baseball?

Każda reguła odczytuje lub usuwa najnowsze wyniki, a anulowanie odsłania poprzedni wynik. To zasada „ostatni na wejściu, pierwszy na wyjściu”, którą stos zapewnia przy operacjach dodawania, usuwania i podglądania w czasie O(1). Tablica używana tylko na końcu działa jak stos.

Czy grę w baseball można rozwiązać przy użyciu O(1) dodatkowej przestrzeni?

Nie zawsze. Ciąg liczb, po którym następuje ciąg wpisów "C", anuluje je w odwrotnej kolejności, więc musisz zapamiętać każdą liczbę, dopóki nie dowiesz się, czy zostanie anulowana. W najgorszym przypadku wymaga to pamięci O(n).

def calPoints(operations):
    # Napisz tutaj kod

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik