Plus One

Q: Berapa kompleksitas waktu Plus One?

Kedua pendekatan berjalan dalam waktu O(n) untuk n digit, karena kasus semua digit 9 menyentuh setiap digit. Versi yang berhenti lebih awal berhenti setelah deretan digit 9 di bagian akhir dan menggunakan ruang tambahan O(1) , kecuali saat jawabannya membutuhkan digit baru di bagian depan.

MudahMatematika dan simulasi

+10

Bilangan bulat nonnegatif disimpan sebagai array digit desimalnya, digits, dengan digit paling signifikan di posisi pertama: 472 adalah [4, 7, 2]. Tambahkan satu ke bilangan tersebut dan kembalikan digit-digit hasilnya dalam bentuk yang sama. Bilangan tersebut dapat memiliki hingga 100 digit, jauh lebih banyak daripada yang dapat ditampung oleh bilangan bulat 64-bit.

Fungsi

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

digitsinteger-array: digit-digit angka, dari yang paling signifikan terlebih dahulu
Mengembalikaninteger-array: digit-digit angka ditambah satu, dari yang paling signifikan terlebih dahulu

Batasan

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits tidak memiliki nol di depan, kecuali untuk angka 0 itu sendiri, yaitu [0].

Contoh

Input: digits = [4, 3, 9]
Output: [4, 4, 0]
Penjelasan: Angkanya adalah 439, dan 439 + 1 = 440. Digit terakhir 9 berubah menjadi 0 dan meneruskan simpanan ke 3, yang menjadi 4.

Input: digits = [0]
Output: [1]
Penjelasan: Angka 0 ditulis sebagai [0], dan 0 + 1 = 1.

Pertanyaan lanjutan

Bagaimana cara mengurangi satu sebagai gantinya, untuk bilangan yang nilainya minimal 1? Kapan hasilnya kehilangan digit pertama, seperti pada [1, 0, 0]?

Solusi

Bilangan 100 digit melampaui kapasitas setiap bilangan bulat 64-bit, yang batasnya sekitar 1.8 × 10^19, jadi kamu tidak bisa mengonversinya lalu menjumlahkannya. Jumlahkan seperti cara di kertas, mulai dari digit terakhir dengan menyimpan angka bawaan. Menambahkan 1 hanya mengubah deretan angka 9 di bagian akhir menjadi angka 0, serta digit di sebelah kirinya.

Penjumlahan dengan menyimpan, digit demi digit

Intuisi

Mulai dengan carry sebesar 1, yaitu angka yang kamu tambahkan. Untuk setiap digit dari kanan, total kolom adalah digit ditambah carry: total % 10 masuk ke jawaban dan total / 10 menjadi carry berikutnya. Total paling besar adalah 9 + 1 = 10, jadi carry tetap 0 atau 1. Carry yang tersisa setelah digit pertama menjadi digit paling depan yang baru, seperti pada 999 + 1 = 1000.

Kamu menghasilkan digit terakhir jawaban terlebih dahulu, jadi kumpulkan digit dengan urutan itu lalu balik urutannya di akhir. Ini membutuhkan waktu O(n) dan array baru dengan hingga n + 1 digit.

Algoritma

Atur carry menjadi 1 dan mulai dengan list kosong untuk jawaban.
Untuk setiap digit dari yang terakhir hingga yang pertama, hitung total = digit + carry.
Tambahkan total % 10 ke jawaban dan atur carry menjadi total / 10, dibulatkan ke bawah.
Setelah perulangan, jika carry adalah 1, tambahkan nilai itu.
Balik urutan jawaban dan kembalikan hasilnya.

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

Berhenti pada digit pertama yang kurang dari 9

Intuisi

Satu digit yang kurang dari 9 menyerap carry sebesar 1: nilainya bertambah satu dan setiap digit di sebelah kirinya mempertahankan nilainya. Hanya digit 9 yang meneruskan carry, dengan berubah menjadi 0. Jadi, kamu bisa berhenti pada digit pertama yang kurang dari 9 dan mengembalikan array input yang diubah langsung. Untuk [2, 9, 0, 9], digit 9 terakhir menjadi 0, digit 0 menjadi 1, lalu kamu mengembalikan [2, 9, 1, 0] tanpa membaca dua digit pertama.

Jika tidak ada digit yang kurang dari 9, bilangannya adalah 10^n - 1 dan jawabannya adalah 1 diikuti n nol. Hanya kasus itu yang memerlukan array baru, jadi selain itu, ruang tambahan yang digunakan adalah O(1).

Algoritma

Telusuri indeks dari yang terakhir hingga yang pertama.
Jika digitnya kurang dari 9, tambahkan nilainya satu dan kembalikan array.
Jika tidak, digitnya adalah 9: atur nilainya menjadi 0 dan pindah satu posisi ke kiri.
Jika perulangan berakhir, semua digit bernilai 9: kembalikan 1 diikuti oleh n angka nol.

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

Jebakan dan kasus tepi

Mengubah array menjadi integer, lalu mengubahnya kembali. Integer 64-bit menampung paling banyak 19 atau 20 digit, jadi 100 digit akan meluap, dan bilangan floating-point kehilangan digit terakhir lebih cepat.
Melupakan digit tambahan. [9, 9, 9] harus menjadi [1, 0, 0, 0]; kode yang hanya menulis ulang tempat yang ada akan menghasilkan [0, 0, 0].
Menambahkan 1 ke digit pertama. Array diurutkan dari digit paling signifikan, jadi digit satuan adalah elemen terakhir.
Tidak langsung mengembalikan nilai setelah digit di bawah 9 menyerap carry. Perulangan kemudian mengubah digit yang seharusnya tetap: [1, 9, 3] harus menjadi [1, 9, 4].
Di Lua dan R, indeks array dimulai dari 1, jadi digit terakhir berada di indeks n, bukan n - 1.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Plus One?

Kedua pendekatan berjalan dalam waktu O(n) untuk n digit, karena kasus semua digit 9 menyentuh setiap digit. Versi yang berhenti lebih awal berhenti setelah deretan digit 9 di bagian akhir dan menggunakan ruang tambahan O(1), kecuali saat jawabannya membutuhkan digit baru di bagian depan.

Mengapa tidak mengubah digit-digit tersebut menjadi bilangan bulat?

Angka tersebut bisa memiliki 100 digit, sedangkan integer 64-bit berhenti di sekitar 1.8 × 10^19, yaitu 20 digit. Python dan Ruby memiliki integer tanpa batas, jadi konversi ini berfungsi di sana, tetapi kodenya tidak bisa diterapkan pada bahasa lain. Memproses digit satu per satu tidak pernah mengalami overflow.

Bagaimana cara menjumlahkan dua angka yang disimpan sebagai array digit?

Gunakan metode kolom dengan satu indeks di akhir setiap array. Setiap kolom menjumlahkan dua digit, menganggap digit yang tidak ada sebagai 0, lalu menambahkan carry. Berhenti saat kedua array sudah habis digunakan dan carry bernilai 0, lalu balik urutan digit yang telah dikumpulkan.

def plusOne(digits):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

digits = [4, 3, 9]

Output yang diharapkan

[4, 4, 0]