Add Two Numbers

Q: Jaka jest złożoność czasowa dodawania dwóch liczb przechowywanych jako listy łączone?

To O(max(L1, L2)) : jeden krok na kolumnę, plus jeszcze jeden, gdy na końcu pozostaje przeniesienie. Oprócz odpowiedzi wersja jednoprzebiegowa używa O(1) pamięci: dwóch wskaźników i przeniesienia.

ŚrednieLista wiązana Matematyka i symulacja

+10

Otrzymujesz dwie nieujemne liczby całkowite, z których każda jest zapisana jako jednokierunkowa lista wiązana cyfr, z najmniej znaczącą cyfrą na początku. W pierwszej liście węzeł i przechowuje cyfrę values1[i] i wskazuje na węzeł next1[i]. Druga lista działa tak samo, używając next2 i values2. W obu listach -1 oznacza koniec listy, a głową jest węzeł 0. Węzły nie są przechowywane w kolejności listy, więc podążaj za wskazaniami.

Zwróć cyfry sumy tych dwóch liczb, zaczynając od najmniej znaczącej cyfry.

Funkcja

addTwoNumbers(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: indeks węzła, do którego prowadzi każdy węzeł pierwszej liczby, lub -1 w przypadku jej ostatniego węzła
values1integer-array: cyfra przechowywana w każdym węźle pierwszej liczby
next2integer-array: indeks węzła, do którego prowadzi każdy węzeł drugiej liczby, lub -1 dla jej ostatniego węzła
values2integer-array: cyfra przechowywana w każdym węźle drugiej liczby
Zwracainteger-array: cyfry sumy, zaczynając od najmniej znaczącej

Ograniczenia

1 ≤ L1 ≤ 100, gdzie L1 jest długością next1 i values1.
1 ≤ L2 ≤ 100, gdzie L2 jest długością next2 i values2.
0 ≤ values1[i], values2[j] ≤ 9
Każdy element next1 ma wartość -1 lub jest indeksem węzła z pierwszej listy, a każdy element next2 ma wartość -1 lub jest indeksem węzła z drugiej listy.
Rozpoczynając od węzła 0, każda z list odwiedza każdy ze swoich węzłów dokładnie raz, a następnie dociera do -1. Nie ma cyklu.
Żadna liczba nie ma zer wiodących: ostatni węzeł listy przechowuje cyfrę inną niż 0, chyba że lista zawiera tylko jedną cyfrę 0.

Przykłady

Wejście: next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
Wyjście: [5, 4, 1, 1]
Wyjaśnienie: Pierwsza lista odwiedza węzły 0, 2, 1 i odczytuje 8, 1, 6, czyli liczbę 618. Druga odczytuje 7, 2, 5, czyli liczbę 527. Ich suma wynosi 1145, więc odpowiedzią jest 5, 4, 1, 1.

Wejście: next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
Wyjście: [0, 0, 0, 0, 1]
Wyjaśnienie: Druga lista odczytuje się jako 1, 9, 9, 9, czyli liczba 9991. Dodanie 9 daje 10000: każda kolumna daje 0 i przeniesienie, a ostatnie przeniesienie staje się piątą cyfrą.

Wejście: next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
Wyjście: [7, 5]
Wyjaśnienie: Pierwsza liczba to 0, a druga lista odczytuje się jako 7, 5, czyli liczba 57. Dodanie 0 niczego nie zmienia, więc odpowiedź to [7, 5].

Pytanie dodatkowe

Jak dodawać liczby, jeśli listy przechowują najbardziej znaczącą cyfrę jako pierwszą?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Liczby są zbyt długie, by zmieścić się w jakimkolwiek typie całkowitym, więc dodawaj je tak jak na papierze: kolumna po kolumnie, przenosząc 1, gdy suma w kolumnie osiągnie 10. Listy przechowują najpierw cyfrę jedności, więc przechodząc po nich, odwiedzasz kolumny w kolejności, w jakiej je dodajesz.

Przepisz cyfry, a następnie dodawaj kolumna po kolumnie

Intuicja

Wskaźnik to tutaj indeks węzła, a przejście dalej to node = next[node]. Skopiuj cyfry każdej listy do tablicy, tak aby indeks i przechowywał cyfrę o wartości 10^i: [8, 1, 6] i [7, 2, 5] w pierwszym przykładzie.

Następnie dodawaj jak na papierze, przyjmując brakującą cyfrę za 0. W każdej kolumnie zapisz sum % 10, a resztę przenieś dalej: 8 + 7 = 15 zapisuje 5 i przenosi 1, 1 + 2 + 1 = 4, a 6 + 5 = 11 zapisuje 1. Ostatnie przeniesienie staje się końcową cyfrą: [5, 4, 1, 1].

Kopie wymagają dodatkowej pamięci O(L1 + L2), której dodawanie w ogóle nie potrzebuje.

Algorytm

Przejdź przez każdą listę od węzła 0 i skopiuj jej cyfry do tablicy.
Ustaw carry = 0. Dla każdego indeksu i aż do długości dłuższej tablicy dodaj istniejące cyfry na pozycji i oraz przeniesienie.
Dodaj sum % 10 i ustaw carry na sum / 10, zaokrąglone w dół.
Jeśli po ostatniej kolumnie przeniesienie wynosi 1, dodaj je.

def readDigits(next, values):
    # The digits in list order: least significant first.
    digits = []
    node = 0
    while node != -1:
        digits.append(values[node])
        node = next[node]
    return digits


def addTwoNumbers(next1, values1, next2, values2):
    first = readDigits(next1, values1)
    second = readDigits(next2, values2)
    result = []
    carry = 0
    for i in range(max(len(first), len(second))):
        column = carry
        if i < len(first):
            column += first[i]
        if i < len(second):
            column += second[i]
        result.append(column % 10)
        carry = column // 10
    if carry > 0:
        result.append(carry)
    return result

Przejdź jednocześnie przez obie listy, przenosząc wartość

Intuicja

Kolumna i korzysta tylko z i-tego węzła każdej listy, więc zachowaj jeden wskaźnik na listę, a i b, i przesuwaj oba w miarę przechodzenia przez kolejne kolumny.

Jedna pętla działa, dopóki a nie jest równe -1 lub b nie jest równe -1, lub przeniesienie wynosi 1. Wskaźnik, który nadal wskazuje węzeł, dodaje jego cyfrę i przechodzi dalej; wskaźnik równy -1 niczego nie dodaje. Dzięki temu obsługiwane są liczby o różnej długości bez drugiej pętli, a warunek przeniesienia dopisuje dodatkową cyfrę na końcu.

W drugim przykładzie, 9 plus 9991, suma w każdej kolumnie wynosi 10 i zapisywane jest 0. Po czterech kolumnach obie listy są już przetworzone, ale przeniesienie wynosi 1, więc pętla wykonuje się jeszcze raz: [0, 0, 0, 0, 1]. Oprócz wyniku przechowuje trzy liczby całkowite.

Algorytm

Ustaw a = 0, b = 0 i carry = 0.
Gdy a != -1 lub b != -1 lub carry > 0, rozpocznij sumowanie kolumny od carry.
Jeśli a != -1, dodaj values1[a] i ustaw a = next1[a]. Zrób to samo dla b, używając drugiej listy.
Dołącz sum % 10 i ustaw carry na sum / 10, zaokrąglone w dół.
Zwróć dołączone cyfry.

def addTwoNumbers(next1, values1, next2, values2):
    a = 0  # current node of the first number
    b = 0  # current node of the second number
    carry = 0
    result = []
    # Keep going while either number has digits left or a carry is waiting.
    while a != -1 or b != -1 or carry > 0:
        column = carry
        if a != -1:
            column += values1[a]
            a = next1[a]
        if b != -1:
            column += values2[b]
            b = next2[b]
        result.append(column % 10)  # the digit this column writes
        carry = column // 10  # 1 when the column reached 10, else 0
    return result

Pułapki i przypadki brzegowe

Konwertowanie każdej listy na liczbę całkowitą i dodawanie. Liczba 100-cyfrowa przekracza zakres każdego typu 64-bitowego.
Pomijanie końcowego przeniesienia. Pętla, która kończy się, gdy obie listy się skończą, zwraca [0, 0, 0, 0] dla drugiego przykładu.
Kończenie, gdy skończy się krótsza lista. W drugim przykładzie powoduje to utratę trzech dziewiątek liczby 9991 i przeniesienia przechodzącego przez nie.
Odczytywanie cyfr w kolejności tablicy. W pierwszym przykładzie values1 ma wartość [8, 6, 1], ale liczba to 618, odczytywana wzdłuż połączeń.
Zapominanie o przesunięciu w Lua i R, gdzie tablice zaczynają się od 1. Zachowaj identyfikatory węzłów indeksowane od 0 i odczytuj next1[node + 1].

Najczęstsze pytania3

Dlaczego cyfry w Add Two Numbers są przechowywane w odwrotnej kolejności?

Dodawanie zaczyna się od cyfry jedności, a po liście jednokierunkowej można poruszać się tylko od jej początku. Gdy najpierw znajduje się cyfra najmniej znacząca, przechodzenie po liście odwiedza kolumny w kolejności, w jakiej je dodajesz, więc przeniesienie przesuwa się do przodu wraz ze wskaźnikami.

Jaka jest złożoność czasowa dodawania dwóch liczb przechowywanych jako listy łączone?

To O(max(L1, L2)): jeden krok na kolumnę, plus jeszcze jeden, gdy na końcu pozostaje przeniesienie. Oprócz odpowiedzi wersja jednoprzebiegowa używa O(1) pamięci: dwóch wskaźników i przeniesienia.

Czy przeniesienie może kiedykolwiek być większe niż 1?

Nie. Kolumna dodaje dwie cyfry o wartości najwyżej 9 oraz przeniesienie o wartości najwyżej 1, więc ich suma wynosi najwyżej 19. Dzielenie przez 10 i zaokrąglenie w dół daje 0 lub 1.

def addTwoNumbers(next1, values1, next2, values2):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

next1 = [2, -1, 1]
values1 = [8, 6, 1]
next2 = [2, -1, 1]
values2 = [7, 5, 2]

Oczekiwany wynik

[5, 4, 1, 1]