Plus One

Q: Jaka jest złożoność czasowa algorytmu Plus One?

Oba podejścia działają w czasie O(n) dla n cyfr, ponieważ w najgorszym przypadku, gdy wszystkie cyfry to 9, sprawdzana jest każda cyfra. Wersja z wcześniejszym zakończeniem zatrzymuje się po końcowych dziewiątkach, więc dla liczby kończącej się cyfrą mniejszą niż 9 wykonuje jeden krok. Używa O(1) dodatkowej pamięci, chyba że wynik wymaga nowej cyfry wiodącej.

Q: Kiedy wynik ma więcej cyfr niż dane wejściowe?

Tylko wtedy, gdy każda cyfra to 9. Wówczas liczba wynosi 10^n - 1 , a dodanie jedynki daje 10^n : 1, po której następuje n zer. Jeśli któraś cyfra jest mniejsza niż 9, przejmuje przeniesienie, więc długość pozostaje taka sama.

ŁatweMatematyka i symulacja

+10

Liczba całkowita nieujemna jest przechowywana jako tablica jej cyfr dziesiętnych, digits, zaczynając od cyfry o najwyższej wartości pozycyjnej: 472 to [4, 7, 2]. Dodaj 1 do liczby i zwróć cyfry wyniku w tej samej postaci. Liczba może mieć do 100 cyfr, czyli znacznie więcej, niż mieści się w liczbie całkowitej 64-bitowej.

Funkcja

plusOne(digits: integer-array) → integer-array

digitsinteger-array: cyfry liczby, od najbardziej znaczącej
Zwracainteger-array: cyfry liczby powiększonej o jeden, od najbardziej znaczącej

Ograniczenia

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits nie zawiera zera wiodącego, z wyjątkiem samej liczby 0, która jest [0].

Przykłady

Wejście: digits = [4, 3, 9]
Wyjście: [4, 4, 0]
Wyjaśnienie: Liczba to 439, a 439 + 1 = 440. Ostatnia cyfra 9 zmienia się w 0 i przenosi jedynkę do 3, które staje się 4.

Wejście: digits = [0]
Wyjście: [1]
Wyjaśnienie: Liczbę 0 zapisuje się jako [0], a 0 + 1 = 1.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak zamiast tego odjąć jeden, gdy liczba wynosi co najmniej 1? Które cyfry się zmieniają i kiedy wynik traci swoją wiodącą cyfrę, jak w przypadku [1, 0, 0]?

Rozwiązanie

Konwersja cyfr na liczbę, dodanie jedynki i ponowna konwersja nie zadziała w tym przypadku: 100 cyfr przekracza zakres każdej liczby całkowitej 64-bitowej, której górna granica wynosi około 1.8 × 10^19. Dlatego dodajesz tak jak na papierze, zaczynając od ostatniej cyfry i przenosząc jedynkę. Jedna obserwacja pozwala skrócić pracę: dodanie 1 zmienia tylko końcowe dziewiątki, które stają się zerami, oraz pierwszą cyfrę po ich lewej stronie. Każda inna cyfra pozostaje bez zmian.

Dodawanie z przeniesieniem, cyfra po cyfrze

Intuicja

Zapisz liczbę i pod spodem dodaj 1 pod jej ostatnią cyfrą, tak jak w szkole. Zacznij z przeniesieniem równym 1 — tej jedynce, którą dodajesz. Dla każdej cyfry, zaczynając od prawej, suma w kolumnie to cyfra plus przeniesienie. Jej ostatnia cyfra, total % 10, trafia do wyniku, a cyfra dziesiątek, total / 10, jest przeniesieniem do następnej kolumny.

Przy przeniesieniu równym 1 suma w kolumnie wynosi najwyżej 9 + 1 = 10, więc przeniesienie zawsze wynosi 0 albo 1. Jeśli po pierwszej cyfrze nadal pozostaje przeniesienie, wynik zyskuje nową cyfrę z przodu: do 999 + 1 potrzebne jest czwarte miejsce na jedynkę z liczby 1000.

Wynik powstaje najpierw od ostatniej cyfry, ponieważ w takiej kolejności go obliczasz. Zbieraj cyfry w ten sposób, a na końcu odwróć ich kolejność. Zajmuje to O(n) czasu i wymaga nowej tablicy o długości do n + 1 cyfr.

Algorytm

Ustaw carry na 1 i rozpocznij od pustej listy z odpowiedzią.
Dla każdej cyfry, od ostatniej do pierwszej, oblicz total = digit + carry.
Dodaj total % 10 do odpowiedzi i ustaw carry na total / 10, zaokrąglone w dół.
Po pętli, jeśli carry wynosi 1, dodaj je.
Odwróć odpowiedź i ją zwróć.

def plusOne(digits):
    result = []  # the answer, last digit first
    carry = 1  # the one you are adding
    for i in range(len(digits) - 1, -1, -1):
        total = digits[i] + carry
        result.append(total % 10)
        carry = total // 10
    if carry > 0:
        result.append(carry)
    result.reverse()
    return result

Zatrzymaj się na pierwszej cyfrze mniejszej niż 9

Intuicja

Zobacz, co dzieje się z przeniesieniem, gdy dodajesz dokładnie 1. Cyfra mniejsza niż 9 przejmuje je: 3 zmienia się w 4, przeniesienie zmienia się na 0, a każda cyfra bardziej z lewej zachowuje swoją wartość. Tylko 9 przekazuje przeniesienie dalej, zmieniając się w 0. Dodanie 1 oznacza więc: zamień końcowe dziewiątki na zera, a następnie dodaj 1 do cyfry bezpośrednio przed nimi.

Przejdź od ostatniej cyfry w lewo. Jeśli trafisz na 9, wpisz 0 i idź dalej. Jeśli trafisz na inną cyfrę, zwiększ ją o jeden i od razu zwróć tablicę, ponieważ żadna cyfra na lewo od niej nie może się zmienić. Dla [2, 9, 0, 9] ostatnia 9 zmienia się w 0, 0 zmienia się w 1 i zatrzymujesz się, otrzymując [2, 9, 1, 0], bez sprawdzania dwóch pierwszych cyfr.

Jeśli pętla nie znajdzie cyfry mniejszej niż 9, każda cyfra była dziewiątką i teraz jest zerem. Liczba wynosiła 10^n - 1, więc odpowiedzią jest 1, po której następuje n zer. Tylko w tym przypadku potrzebna jest nowa tablica. We wszystkich pozostałych przypadkach zmieniasz dane wejściowe w miejscu, więc dodatkowe miejsce wynosi O(1), a pętla wykonuje się raz dla każdej końcowej dziewiątki i jeszcze jeden raz.

Algorytm

Przejdź przez indeksy od ostatniego do pierwszego.
Jeśli cyfra jest mniejsza niż 9, zwiększ ją o jeden i zwróć tablicę.
W przeciwnym razie cyfra wynosi 9: ustaw ją na 0 i przesuń się o jedno miejsce w lewo.
Jeśli pętla się zakończy, każda cyfra wynosiła 9: zwróć 1, po którym następuje n zer.

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1  # no carry leaves this digit, so the rest stays as it is
            return digits
        digits[i] = 0  # 9 + 1 = 10: write 0 and carry one to the left
    # Every digit was 9: the answer is 1 followed by zeros.
    return [1] + digits

Pułapki i przypadki brzegowe

Pułapkami są przepełnienie liczby całkowitej i przypadek samych dziewiątek.

Zamiana tablicy na liczbę całkowitą i z powrotem. Przechodzi małe testy, a potem nie przechodzi testów ze 100-cyfrowymi liczbami: liczba 64-bitowa mieści co najwyżej 19 lub 20 cyfr, a liczba zmiennoprzecinkowa traci ostatnie cyfry jeszcze wcześniej.
Zapomnienie o dodatkowej cyfrze. [9, 9, 9] musi zmienić się w [1, 0, 0, 0], czyli cztery cyfry. Kod, który zmienia tylko istniejące miejsca, zwraca [0, 0, 0].
Dodanie 1 do pierwszej cyfry zamiast do ostatniej. Tablica jest zapisana od najbardziej znaczącej cyfry, więc cyfra jedności znajduje się na końcu.
Zapomnienie o zwróceniu wyniku po tym, jak cyfra mniejsza niż 9 przejmie przeniesienie. W wersji z wcześniejszym zakończeniem pętla działa dalej i zmienia cyfry, które powinny pozostać bez zmian. W [1, 9, 3] może zmienić się tylko 3; odpowiedź to [1, 9, 4].
Pomylenie kolejności indeksów w Lua i R, gdzie tablice zaczynają się od 1: ostatnia cyfra znajduje się pod indeksem n, a nową wiodącą 1 umieszcza się przed indeksem 1.

Najczęstsze pytania4

Jaka jest złożoność czasowa algorytmu Plus One?

Oba podejścia działają w czasie O(n) dla n cyfr, ponieważ w najgorszym przypadku, gdy wszystkie cyfry to 9, sprawdzana jest każda cyfra. Wersja z wcześniejszym zakończeniem zatrzymuje się po końcowych dziewiątkach, więc dla liczby kończącej się cyfrą mniejszą niż 9 wykonuje jeden krok. Używa O(1) dodatkowej pamięci, chyba że wynik wymaga nowej cyfry wiodącej.

Dlaczego nie zamienić cyfr na liczbę całkowitą?

Ponieważ liczba może mieć 100 cyfr, a liczba całkowita 64-bitowa kończy się na około 1.8 × 10^19, czyli 20 cyfrach. Python i Ruby obsługują liczby całkowite o nieograniczonej wielkości, więc konwersja działa w tych językach, ale przesłania sens ćwiczenia i nie sprawdza się w innych językach. Przetwarzanie cyfry po cyfrze nigdy nie powoduje przepełnienia.

Kiedy wynik ma więcej cyfr niż dane wejściowe?

Tylko wtedy, gdy każda cyfra to 9. Wówczas liczba wynosi 10^n - 1, a dodanie jedynki daje 10^n: 1, po której następuje n zer. Jeśli któraś cyfra jest mniejsza niż 9, przejmuje przeniesienie, więc długość pozostaje taka sama.

Jak dodać dwie liczby zapisane jako tablice cyfr?

Użyj metody kolumnowej z pierwszego podejścia, korzystając z dwóch indeksów — po jednym na końcu każdej tablicy. W każdej kolumnie dodaj dwie cyfry, traktując brakującą cyfrę jako 0, oraz przeniesienie. Kontynuuj, aż wykorzystasz obie tablice i przeniesienie będzie równe 0, a następnie odwróć zebrane cyfry.

Python

def plusOne(digits):
    # Wpisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

digits = [4, 3, 9]

Oczekiwane

[4, 4, 0]