Add Two Numbers

Q: Bağlı listeler olarak saklanan iki sayıyı toplamanın zaman karmaşıklığı nedir?

O(max(L1, L2)) değerindedir: sütun başına bir adım, ayrıca sonunda elde kalırsa bir adım daha. Yanıt dışında, tek geçişli sürüm O(1) bellek kullanır: iki işaretçi ve elde.

OrtaBağlı liste Matematik ve simülasyon

+10

İki negatif olmayan tam sayı alırsın; her biri, basamaklarının en küçük anlamlı basamak önce gelecek şekilde tek yönlü bağlı liste olarak saklanır. İlk listede i düğümü values1[i] basamağını tutar ve next1[i] düğümüne bağlanır. İkinci liste de next2 ve values2 ile aynı şekilde çalışır. Her iki listede de -1 listenin sonunu belirtir ve baş düğüm 0'dır. Düğümler liste sırasına göre saklanmadığından bağlantıları takip et.

İki sayının toplamının basamaklarını, en küçük anlamlı basamak önce gelecek şekilde döndür.

Fonksiyon

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

next1integer-array: ilk sayının her bir düğümünün bağlandığı düğümün indeksi veya son düğümü için -1
values1integer-array: İlk sayının her düğümünde tutulan rakam
next2integer-array: ikinci sayının her düğümünün bağlandığı düğümün indeksi veya son düğümü için -1
values2integer-array: İkinci sayının her düğümünde tutulan rakam
Döndürürinteger-array: toplamın basamakları, en düşük basamaktan başlayarak

Kısıtlar

1 ≤ L1 ≤ 100; burada L1, next1 ve values1 uzunluğudur.
1 ≤ L2 ≤ 100; burada L2, next2 ve values2 uzunluğudur.
0 ≤ values1[i], values2[j] ≤ 9
next1 öğesinin her bir girdisi -1 ya da ilk listenin bir düğüm dizinidir ve next2 öğesinin her bir girdisi -1 ya da ikinci listenin bir düğüm dizinidir.
0 düğümünden başlayarak her liste, düğümlerinin her birini tam olarak bir kez ziyaret eder ve ardından -1 değerine ulaşır. Döngü yoktur.
Hiçbir sayının başında sıfır bulunmaz: Liste tek basamaklı 0 sayısından oluşmadığı sürece, listenin son düğümü 0 dışında bir rakam içerir.

Örnekler

Girdi: next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
Çıktı: [5, 4, 1, 1]
Açıklama: İlk liste 0, 2, 1 düğümlerini ziyaret eder ve 8, 1, 6 değerlerini okuyarak 618 sayısını oluşturur. İkinci liste 7, 2, 5 değerlerini okuyarak 527 sayısını oluşturur. Toplamları 1145 olduğundan cevap 5, 4, 1, 1 olur.

Girdi: next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
Çıktı: [0, 0, 0, 0, 1]
Açıklama: İkinci liste, 9991 sayısı olan 1, 9, 9, 9 şeklinde okunur. 9 eklemek 10000 sonucunu verir: her sütun bir 0 ve bir elde üretir; son elde beşinci basamak olur.

Girdi: next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
Çıktı: [7, 5]
Açıklama: İlk sayı 0'dır ve ikinci liste 7, 5 şeklinde okunur; yani sayı 57'dir. 0 eklemek hiçbir şeyi değiştirmez, bu yüzden cevap [7, 5] olur.

Ek soru

Listeler en anlamlı basamağı ilk sırada tutuyorsa sayıları nasıl toplardın?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Sayılar herhangi bir tam sayı türü için fazla uzun, bu yüzden onları kâğıt üzerinde olduğu gibi toplayın: sütun sütun, bir sütunun toplamı 10'a ulaştığında 1 elde taşıyarak. Listeler birler basamağını ilk sırada saklar; bu nedenle listeler üzerinde ilerlemek, sütunları topladığınız sırayla ziyaret eder.

Rakamları dışarı kopyalayın, ardından sütun sütun toplayın

Sezgi

Buradaki işaretçi bir düğüm indeksidir ve ileri gitmek node = next[node] demektir. Her listenin rakamlarını bir diziye kopyalayın; böylece i indeksi 10^i değerindeki rakamı tutar: ilk örnekte [8, 1, 6] ve [7, 2, 5].

Ardından, eksik bir rakamı 0 sayarak kâğıt üzerinde toplar gibi toplayın. Her basamakta sum % 10 yazılır ve kalan elde olarak aktarılır: 8 + 7 = 15, 5 yazar ve 1 elde verir; 1 + 2 + 1 = 4 olur ve 6 + 5 = 11, 1 yazar. Son elde son rakama dönüşür: [5, 4, 1, 1].

Kopyalar, toplama işleminin hiç ihtiyaç duymadığı O(L1 + L2) ek bellek kullanır.

Algoritma

Her listeyi 0 düğümünden başlayarak dolaşın ve rakamlarını bir diziye kopyalayın.
carry = 0 olarak ayarlayın. Daha uzun dizinin uzunluğuna kadar her i indeksi için, varsa i konumundaki rakamları ve eldeyi toplayın.
sum % 10 değerini ekleyin ve carry değerini aşağı yuvarlanmış sum / 10 olarak ayarlayın.
Son sütundan sonra elde 1 ise bunu ekleyin.

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

Taşıma değeriyle iki listeyi aynı anda dolaş

Sezgi

i sütunu her listenin yalnızca i. düğümünü kullandığından, her liste için birer işaretçi, a ve b tut ve sütunlar ilerledikçe ikisini de ilerlet.

Bir döngü, a -1 olmadığı, b -1 olmadığı veya elde 1 olduğu sürece çalışır. Hâlâ düğümü olan bir işaretçi kendi basamağını toplama ekler ve ilerler; -1 konumundaki bir işaretçi hiçbir şey eklemez. Bu, ikinci bir döngüye gerek kalmadan farklı uzunluktaki sayıları işler ve elde koşulu sondaki fazladan basamağı yazar.

İkinci örnekte, 9 artı 9991 işleminde her sütunun toplamı 10 olur ve 0 yazılır. Dört sütundan sonra her iki liste de tamamlanır, ancak elde 1 olduğundan döngü bir kez daha çalışır: [0, 0, 0, 0, 1]. Yanıt dışında üç tamsayı tutar.

Algoritma

a = 0, b = 0 ve carry = 0 olarak ayarla.
a != -1 veya b != -1 veya carry > 0 olduğu sürece, sütun toplamını carry ile başlat.
a != -1 ise values1[a] değerini ekle ve a = next1[a] olarak ayarla. İkinci liste için b ile aynısını yap.
sum % 10 değerini ekle ve carry değerini aşağı yuvarlanmış sum / 10 olarak ayarla.
Eklediğin rakamları döndür.

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

Tuzaklar ve uç durumlar

Her listeyi tam sayıya dönüştürüp toplamak. 100 basamaklı bir sayı her 64 bitlik türde taşmaya yol açar.
Son eldeyi atlamak. Her iki liste de bittiğinde duran bir döngü, ikinci örnek için [0, 0, 0, 0] değerini döndürür.
Daha kısa liste bittiğinde durmak. Böylece ikinci örnekte 9991'in üç 9'u ve bu rakamlar boyunca ilerleyen elde kaybolur.
Rakamları dizi sırasına göre okumak. İlk örnekte values1, [8, 6, 1] değeridir; ancak bağlantılar boyunca okunan sayı 618'dir.
Dizilerin 1'den başladığı Lua ve R'de ofseti unutmak. Düğüm kimliklerini 0 tabanlı tutun ve next1[node + 1] ifadesini okuyun.

Sıkça sorulan sorular3

İki Sayıyı Topla'da rakamlar neden ters sırada saklanıyor?

Toplama birler basamağından başlar ve tek yönlü bağlı bir listede yalnızca başından itibaren ilerlenebilir. En düşük basamak ilk sırada olduğunda, liste ekleme yaptığınız sütunları sırayla dolaşır; böylece elde, işaretçilerle birlikte ileri taşınır.

Bağlı listeler olarak saklanan iki sayıyı toplamanın zaman karmaşıklığı nedir?

O(max(L1, L2)) değerindedir: sütun başına bir adım, ayrıca sonunda elde kalırsa bir adım daha. Yanıt dışında, tek geçişli sürüm O(1) bellek kullanır: iki işaretçi ve elde.

Taşıma değeri hiç 1'den büyük olabilir mi?

Hayır. Bir sütun, en fazla 9 olan iki basamağı ve en fazla 1 olan eldeyi toplar; dolayısıyla toplam en fazla 19 olur. 10'a bölüp aşağı yuvarlayınca 0 veya 1 elde edilir.

def addTwoNumbers(next1, values1, next2, values2):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

[5, 4, 1, 1]