Baseball Game

Q: Czy Baseball Game można rozwiązać przy użyciu dodatkowej pamięci O(1)?

Nie zawsze. Seria liczb, po której następuje seria 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) . Bieżąca suma pozwala pominąć końcowe przejście, ale nie stos.

Q: Jak odróżnić liczbę od operacji w Baseball Game?

Najpierw porównaj wpis z trzema symbolami "+" , "D" i "C" , a wszystko inne potraktuj jako liczbę całkowitą. Konwersja za pomocą parsera języka obsługuje początkowy znak minus, więc "-30000" staje się -30000 .

ŁatweStos

+10

Prowadzisz punktację w nietypowej grze. Lista operations jest odczytywana od lewej do prawej, a każdy wpis zmienia rejestr wyników. Liczba całkowita, taka jak "7" lub "-2", dodaje ten wynik do rejestru. "+" dodaje wynik równy sumie dwóch ostatnich wyników, "D" dodaje wynik równy dwukrotności ostatniego wyniku, a "C" na stałe usuwa ostatni wynik z rejestru.

Napisz funkcję o nazwie calPoints, która zwraca sumę wyników pozostających w rejestrze po ostatniej operacji. Suma pustego rejestru wynosi 0.

Funkcja

calPoints(operations: string-array) → integer

operationsstring-array: operacje w kolejności: liczby całkowite jako tekst lub "+", "D", "C"
Zwracainteger: suma wyników, które nadal są w zapisie na końcu

Ograniczenia

1 ≤ operations.length ≤ 5000
Każdy wpis to "+", "D", "C" lub liczba całkowita zapisana w systemie dziesiętnym, dla której -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Każda operacja jest poprawna: "+" występuje tylko wtedy, gdy rekord zawiera co najmniej dwa wyniki, a "D" i "C" tylko wtedy, gdy zawiera co najmniej jeden.
Każdy wynik w rekordzie 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: Wynik rośnie do [4, -2], "D" dodaje -4, "+" dodaje -2 + -4 = -6, "C" usuwa to -6, a 7 trafia na koniec. Wynik [4, -2, -4, 7] daje sumę 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 pozostaje, 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] sumuje się do 21.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz zwrócić sumę bez dodawania rekordu na końcu, tak aby każda operacja, w tym anulowanie, zajmowała O(1) czasu?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każda operacja sprawdza najnowsze wyniki, a "C" może zdejmować wyniki po jednym, więc wyniki sprzed anulowanego wyniku znów stają się najnowsze. Ten schemat „ostatni na wejściu, pierwszy na wyjściu” to właśnie stos. Dodaj każdy nowy wynik na stos, zdejmij wynik po "C" i odczytaj jeden lub dwa elementy ze szczytu przy "D" i "+".

Twórz rekord na stosie, zsumuj go na końcu

Intuicja

Przechowuj wyniki na liście, tak aby najnowszy wynik znajdował się na jej końcu. Wtedy każda operacja dotyczy tylko końca listy: liczba całkowita jest dodawana na końcu, "D" dodaje na końcu dwukrotność ostatniego elementu, "+" dodaje na końcu sumę dwóch ostatnich elementów, a "C" usuwa ostatni element.

Dlaczego stos wystarczy: po "C" wynikiem drugim od końca staje się najnowszy wynik, który musi odczytać następne "D" lub "+". Usunięcie elementu ze stosu daje ci to za darmo. W pierwszym przykładzie "C" usuwa -6 i pozostawia [4, -2, -4], więc każde późniejsze "+" ponownie dodałoby -2 + -4.

Gdy skończą się operacje, lista zawiera dokładnie te wyniki, które się liczą. Dodaj je do siebie. Każda operacja zajmuje O(1), a końcowa suma O(n), więc całość działa w czasie O(n), a stos zajmuje O(n) pamięci.

Algorytm

Zacznij od pustego stosu record.
W przypadku "+" dodaj sumę dwóch elementów na szczycie stosu. W przypadku "D" dodaj dwukrotność elementu na szczycie stosu.
W przypadku "C" zdejmij element ze szczytu stosu.
W przeciwnym razie wpis jest liczbą: zamień tekst na liczbę całkowitą i dodaj ją na stos.
Zwróć sumę wszystkich elementó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

Końcowa pętla przechodząca po stosie to dodatkowa praca, której możesz uniknąć. Zachowuj zmienną total, która zawsze jest równa sumie elementów stosu. Każde dodanie elementu zwiększa total o nowy wynik, a każde "C" odejmuje wynik usunięty ze stosu.

Stos nadal jest potrzebny. Anulowanie musi wiedzieć, który wynik odjąć od sumy, a "+" i "D" muszą znać najnowsze wyniki po ewentualnych anulowaniach. W pierwszym przykładzie suma zmienia się kolejno na 4, 2, -2, -8, następnie anulowanie usuwa z niej -6, dając -2, a końcowe 7 zwiększa ją do 5.

Złożoność czasowa wynosi O(n) przy jednym przejściu, a odpowiedź jest gotowa po dowolnym prefiksie operacji, co ma znaczenie, gdy wyniki napływają na bieżąco. Złożoność pamięciowa wynosi O(n): wszystkie n operacji mogą być liczbami, które pozostają w zapisie.

Algorytm

Zacznij od pustego stosu record i total = 0.
W przypadku "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

Zasady są krótkie, więc większość błędów wynika z odczytania niewłaściwego wyniku lub niepoprawnego parsowania tekstu.

Przechowywanie tylko bieżącej sumy i dwóch ostatnich wyników. Po "C" potrzebujesz wyniku sprzed tych dwóch, więc anulowanie, po którym następuje "+", odczytuje nieaktualne wartości. Zachowaj cały stos.
Zapominanie, że anulowane wyniki są odejmowane od sumy. Przy bieżącej sumie "C" musi odjąć usunięty wynik, a nie go zignorować.
Ręczne parsowanie wyników ujemnych i pomijanie znaku. Użyj parsera liczb całkowitych w danym języku, który odczytuje "-2" jako -2.
Sprawdzanie, czy wpis jest liczbą, przez sprawdzenie, czy zawiera cyfrę. "-5" zaczyna się od znaku minus; sprawdzaj trzy symbole, a wszystko inne traktuj jako liczbę.
Zakładanie, że odpowiedź jest dodatnia. Ujemne wyniki i anulowania mogą dać ujemną sumę lub 0, gdy anulowano wszystkie wyniki.

Najczęstsze pytania4

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

Każda operacja wykonuje stałą ilość pracy na szczycie stosu, więc przetworzenie n operacji zajmuje czas O(n). Zsumowanie wartości na stosie na końcu zajmuje najwyżej kolejne O(n), a bieżąca suma eliminuje nawet tę potrzebę. Stos zajmuje O(n) pamięci, gdy większość operacji dodaje wyniki.

Dlaczego stos jest odpowiednią strukturą danych w grze Baseball Game?

Każda reguła odczytuje lub usuwa najnowsze wyniki, a anulowanie odsłania wynik, który pojawił się wcześniej. To kolejność ostatni na wejściu, pierwszy na wyjściu, którą zapewnia stos z operacjami push, pop i peek w czasie O(1). Zwykła tablica lub lista, z której korzysta się tylko na jej końcu, działa jak stos w każdym języku.

Czy Baseball Game można rozwiązać przy użyciu dodatkowej pamięci O(1)?

Nie zawsze. Seria liczb, po której następuje seria 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). Bieżąca suma pozwala pominąć końcowe przejście, ale nie stos.

Jak odróżnić liczbę od operacji w Baseball Game?

Najpierw porównaj wpis z trzema symbolami "+", "D" i "C", a wszystko inne potraktuj jako liczbę całkowitą. Konwersja za pomocą parsera języka obsługuje początkowy znak minus, więc "-30000" staje się -30000.

Python

def calPoints(operations):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane