Add Two Numbers

Q: Apa kompleksitas waktu untuk menjumlahkan dua angka yang disimpan sebagai linked list?

Kompleksitasnya O(max(L1, L2)) : satu langkah per kolom, ditambah satu langkah lagi jika masih ada carry di akhir. Selain jawaban, versi satu lintasan menggunakan memori O(1) : dua pointer dan carry.

SedangLinked list Matematika dan simulasi

+10

Kamu mendapatkan dua bilangan bulat nonnegatif, masing-masing disimpan sebagai linked list satu arah yang berisi digit-digitnya, dengan digit paling tidak signifikan di awal. Pada list pertama, node i menyimpan digit values1[i] dan terhubung ke node next1[i]. List kedua bekerja dengan cara yang sama menggunakan next2 dan values2. Pada kedua list, -1 menandai akhir list dan head-nya adalah node 0. Node-node tersebut tidak disimpan sesuai urutan dalam list, jadi ikuti tautannya.

Kembalikan digit-digit hasil penjumlahan kedua bilangan tersebut, dengan digit paling tidak signifikan di awal.

Fungsi

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

next1integer-array: indeks node yang ditautkan oleh setiap node dari angka pertama, atau -1 untuk node terakhirnya
values1integer-array: digit yang disimpan oleh setiap node dari bilangan pertama
next2integer-array: indeks node yang ditautkan oleh setiap node dari angka kedua, atau -1 untuk node terakhirnya
values2integer-array: digit yang disimpan oleh setiap node dari bilangan kedua
Mengembalikaninteger-array: digit-digit hasil penjumlahan, dimulai dari yang paling tidak signifikan

Batasan

1 ≤ L1 ≤ 100, dengan L1 adalah panjang next1 dan values1.
1 ≤ L2 ≤ 100, dengan L2 sebagai panjang next2 dan values2.
0 ≤ values1[i], values2[j] ≤ 9
Setiap entri next1 adalah -1 atau indeks node dari list pertama, dan setiap entri next2 adalah -1 atau indeks node dari list kedua.
Dimulai dari node 0, setiap list mengunjungi semua node-nya tepat satu kali, lalu mencapai -1. Tidak ada siklus.
Tidak ada angka yang memiliki nol di depan: node terakhir dalam list menyimpan digit selain 0, kecuali jika list tersebut hanya berisi digit 0.

Contoh

Input: next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
Output: [5, 4, 1, 1]
Penjelasan: List pertama mengunjungi node 0, 2, 1 dan membaca 8, 1, 6, yaitu angka 618. List kedua membaca 7, 2, 5, yaitu angka 527. Jumlahnya 1145, jadi jawabannya adalah 5, 4, 1, 1.

Input: next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
Output: [0, 0, 0, 0, 1]
Penjelasan: List kedua terbaca sebagai 1, 9, 9, 9, yaitu angka 9991. Menambahkan 9 menghasilkan 10000: setiap kolom menghasilkan 0 dan sebuah angka simpanan, lalu angka simpanan terakhir menjadi digit kelima.

Input: next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
Output: [7, 5]
Penjelasan: Angka pertama adalah 0 dan list kedua menunjukkan 7, 5, yaitu angka 57. Menambahkan 0 tidak mengubah apa pun, jadi jawabannya adalah [7, 5].

Pertanyaan lanjutan

Bagaimana kamu menjumlahkan angkanya jika list menyimpan digit paling signifikan di urutan pertama?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Angkanya terlalu panjang untuk tipe integer apa pun, jadi jumlahkan seperti di atas kertas: kolom demi kolom, bawa 1 saat sebuah kolom mencapai 10. List menyimpan digit satuan terlebih dahulu, jadi menelusurinya akan mengunjungi kolom-kolom sesuai urutan penjumlahannya.

Salin digit-digitnya, lalu jumlahkan kolom demi kolom

Intuisi

Pointer di sini adalah indeks node, dan untuk maju gunakan node = next[node]. Salin digit setiap list ke dalam array, sehingga indeks i menyimpan digit dengan nilai 10^i: [8, 1, 6] dan [7, 2, 5] pada contoh pertama.

Lalu jumlahkan seperti di atas kertas, dengan menghitung digit yang tidak ada sebagai 0. Setiap kolom menuliskan sum % 10 dan membawa sisanya: 8 + 7 = 15 menuliskan 5 dan membawa 1, 1 + 2 + 1 = 4, dan 6 + 5 = 11 menuliskan 1. Sisa terakhir menjadi digit akhir: [5, 4, 1, 1].

Penyalinan ini membutuhkan memori tambahan sebesar O(L1 + L2) yang tidak pernah diperlukan oleh penjumlahan.

Algoritma

Telusuri setiap list mulai dari node 0 dan salin digitnya ke dalam array.
Tetapkan carry = 0. Untuk setiap indeks i hingga panjang array yang lebih panjang, jumlahkan digit pada i yang tersedia dan carry.
Tambahkan sum % 10 dan tetapkan carry ke sum / 10, dibulatkan ke bawah.
Jika carry bernilai 1 setelah kolom terakhir, tambahkan carry tersebut.

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

Telusuri kedua list sekaligus dengan nilai bawaan

Intuisi

Kolom i hanya menggunakan node ke-i dari setiap list, jadi gunakan satu penunjuk untuk setiap list, a dan b, lalu gerakkan keduanya seiring kolom bertambah.

Satu perulangan berjalan selama a bukan -1, atau b bukan -1, atau nilai bawaan adalah 1. Penunjuk yang masih memiliki node akan menambahkan digitnya lalu bergerak maju; penunjuk pada -1 tidak menambahkan apa pun. Cara ini menangani angka dengan panjang berbeda tanpa perulangan kedua, dan kondisi nilai bawaan menuliskan digit tambahan di akhir.

Pada contoh kedua, 9 ditambah 9991, setiap kolom berjumlah 10 dan menuliskan 0. Setelah empat kolom, kedua list selesai, tetapi nilai bawaan adalah 1, jadi perulangan berjalan sekali lagi: [0, 0, 0, 0, 1]. Selain jawaban, cara ini hanya menggunakan tiga bilangan bulat.

Algoritma

Tetapkan a = 0, b = 0 dan carry = 0.
Selama a != -1 atau b != -1 atau carry > 0, mulai jumlah kolom dengan carry.
Jika a != -1, tambahkan values1[a] dan tetapkan a = next1[a]. Lakukan hal yang sama untuk b dengan list kedua.
Tambahkan sum % 10 dan tetapkan carry ke sum / 10, dibulatkan ke bawah.
Kembalikan digit yang kamu tambahkan.

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

Jebakan dan kasus tepi

Mengubah setiap list menjadi bilangan bulat lalu menjumlahkannya. Bilangan 100 digit melampaui kapasitas semua tipe 64-bit.
Mengabaikan carry terakhir. Perulangan yang berhenti saat kedua list habis akan menghasilkan [0, 0, 0, 0] untuk contoh kedua.
Berhenti saat list yang lebih pendek habis. Akibatnya, contoh kedua kehilangan tiga angka 9 dari 9991 dan carry yang merambat melewatinya.
Membaca digit sesuai urutan array. Dalam contoh pertama, values1 adalah [8, 6, 1], tetapi bilangannya adalah 618, dibaca mengikuti tautannya.
Lupa memperhitungkan offset di Lua dan R, yang array-nya dimulai dari 1. Pertahankan ID node berbasis 0 dan baca next1[node + 1].

Pertanyaan yang sering diajukan3

Mengapa digit disimpan dalam urutan terbalik di Add Two Numbers?

Penjumlahan dimulai dari digit satuan, dan singly linked list hanya bisa ditelusuri dari head-nya. Jika digit paling tidak signifikan berada di urutan pertama, penelusuran mengunjungi kolom sesuai urutan penjumlahannya, sehingga carry bergerak maju bersama pointer.

Apa kompleksitas waktu untuk menjumlahkan dua angka yang disimpan sebagai linked list?

Kompleksitasnya O(max(L1, L2)): satu langkah per kolom, ditambah satu langkah lagi jika masih ada carry di akhir. Selain jawaban, versi satu lintasan menggunakan memori O(1): dua pointer dan carry.

Apakah carry bisa lebih besar dari 1?

Tidak. Satu kolom menjumlahkan dua digit yang masing-masing paling besar 9 dan satu simpanan paling besar 1, sehingga jumlahnya paling besar 19. Membaginya dengan 10 lalu membulatkannya ke bawah menghasilkan 0 atau 1.

def addTwoNumbers(next1, values1, next2, values2):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

[5, 4, 1, 1]