Plus One

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

Oba podejścia działają w czasie O(n) dla n cyfr, ponieważ przypadek z samymi dziewiątkami wymaga sprawdzenia każdej cyfry. Wersja z wcześniejszym zakończeniem zatrzymuje się po końcowych dziewiątkach i używa dodatkowej pamięci O(1) , z wyjątkiem sytuacji, gdy wynik wymaga nowej cyfry wiodącej.

ŁatweMatematyka i symulacja

+10

Nieujemna liczba całkowita jest przechowywana jako tablica jej cyfr dziesiętnych, digits, zaczynając od najbardziej znaczącej cyfry: 472 to [4, 7, 2]. Dodaj jeden do tej 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 64-bitowej.

Funkcja

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

digitsinteger-array: cyfry liczby, od najbardziej znaczącej
Zwracainteger-array: cyfry liczby plus jeden, od najbardziej znaczącej

Ograniczenia

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits nie ma zera wiodącego, z wyjątkiem samej liczby 0, która jest równa [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óra staje się 4.

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

Pytanie dodatkowe

Jak zamiast tego odjąć jeden, gdy liczba wynosi co najmniej 1? Kiedy wynik traci swoją wiodącą cyfrę, jak w przypadku [1, 0, 0]?

Rozwiązanie

Liczba 100-cyfrowa przekracza zakres każdej liczby całkowitej 64-bitowej, który kończy się w pobliżu 1.8 × 10^19, więc nie możesz jej przekonwertować i dodać. Dodawaj tak jak na papierze, zaczynając od ostatniej cyfry i przenosząc jedynkę. Dodanie 1 zmienia tylko końcowe dziewiątki, które stają się zerami, oraz cyfrę po ich lewej stronie.

Dodawanie z przeniesieniem, cyfra po cyfrze

Intuicja

Zacznij od przeniesienia 1, czyli liczby, którą dodajesz. Dla każdej cyfry, zaczynając od prawej, suma w kolumnie to cyfra plus przeniesienie: total % 10 trafia do wyniku, a total / 10 jest kolejnym przeniesieniem. Suma wynosi najwyżej 9 + 1 = 10, więc przeniesienie pozostaje równe 0 lub 1. Przeniesienie pozostałe po pierwszej cyfrze staje się nową cyfrą wiodącą, jak w przypadku 999 + 1 = 1000.

Wynik tworzysz od ostatniej cyfry, więc zbieraj cyfry w tej kolejności i odwróć je na końcu. Zajmuje to O(n) czasu i wymaga utworzenia nowej tablicy zawierającej maksymalnie n + 1 cyfr.

Algorytm

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

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ę przy pierwszej cyfrze mniejszej niż 9

Intuicja

Cyfra mniejsza niż 9 przyjmuje przeniesienie 1: zwiększa się o jeden, a każda cyfra po jej lewej stronie zachowuje swoją wartość. Tylko 9 przekazuje przeniesienie dalej, zmieniając się w 0. Możesz więc zatrzymać się na pierwszej cyfrze mniejszej niż 9 i zwrócić tablicę wejściową, zmodyfikowaną bezpośrednio. Dla [2, 9, 0, 9] ostatnia 9 zmienia się w 0, 0 zmienia się w 1, a ty zwracasz [2, 9, 1, 0] bez odczytywania pierwszych dwóch cyfr.

Jeśli żadna cyfra nie jest mniejsza niż 9, liczba wynosiła 10^n - 1, a wynikiem jest 1, po której następuje n zer. Tylko w tym przypadku potrzebna jest nowa tablica, więc w pozostałych przypadkach dodatkowa przestrzeń wynosi O(1).

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 była równa 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

Konwertowanie tablicy na liczbę całkowitą i z powrotem. Liczba całkowita 64-bitowa mieści najwyżej 19 lub 20 cyfr, więc 100 cyfr powoduje przepełnienie, a liczba zmiennoprzecinkowa traci ostatnie cyfry jeszcze wcześniej.
Zapomnienie o dodatkowej cyfrze. [9, 9, 9] musi zmienić się w [1, 0, 0, 0]; kod, który przepisuje tylko istniejące miejsca, zwraca [0, 0, 0].
Dodawanie 1 do pierwszej cyfry. Tablica jest uporządkowana od najbardziej znaczącej cyfry, więc cyfra jedności znajduje się na ostatnim miejscu.
Brak zwrócenia wyniku, gdy cyfra mniejsza niż 9 przejmuje przeniesienie. Pętla zmienia wtedy cyfry, które powinny pozostać bez zmian: [1, 9, 3] musi zmienić się w [1, 9, 4].
W Lua i R tablice zaczynają się od 1, więc ostatnia cyfra ma indeks n, a nie n - 1.

Najczęstsze pytania3

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

Oba podejścia działają w czasie O(n) dla n cyfr, ponieważ przypadek z samymi dziewiątkami wymaga sprawdzenia każdej cyfry. Wersja z wcześniejszym zakończeniem zatrzymuje się po końcowych dziewiątkach i używa dodatkowej pamięci O(1), z wyjątkiem sytuacji, gdy wynik wymaga nowej cyfry wiodącej.

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

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 kod nie przenosi się na inne języki. Przetwarzanie cyfry po cyfrze nigdy nie powoduje przepełnienia.

Jak dodać dwie liczby zapisane jako tablice cyfr?

Użyj metody kolumnowej z jednym indeksem na końcu każdej tablicy. W każdej kolumnie dodaj do siebie dwie cyfry, przyjmując 0 za brakującą cyfrę, oraz przeniesienie. Zakończ, gdy wykorzystasz obie tablice, a przeniesienie będzie równe 0, a następnie odwróć zebrane cyfry.

def plusOne(digits):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

digits = [4, 3, 9]

Oczekiwany wynik

[4, 4, 0]