Plus One

Q: Độ phức tạp thời gian của Plus One là gì?

Cả hai cách đều chạy trong thời gian O(n) với n chữ số, vì trường hợp toàn số 9 sẽ xử lý mọi chữ số. Phiên bản thoát sớm dừng sau các số 9 ở cuối và dùng thêm O(1) dung lượng, trừ khi đáp án cần thêm một chữ số ở đầu.

DễToán và mô phỏng

+10

Một số nguyên không âm được lưu dưới dạng mảng các chữ số thập phân, digits, với chữ số có giá trị lớn nhất đứng trước: 472 là [4, 7, 2]. Hãy cộng thêm một vào số đó rồi trả về các chữ số của kết quả theo cùng định dạng. Số này có thể có tới 100 chữ số, nhiều hơn rất nhiều so với sức chứa của số nguyên 64 bit.

Hàm

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

digitsinteger-array: các chữ số của số đó, từ chữ số có giá trị lớn nhất đến chữ số có giá trị nhỏ nhất
Trả vềinteger-array: các chữ số của số đó cộng thêm một, theo thứ tự từ chữ số có giá trị lớn nhất đến chữ số có giá trị nhỏ nhất

Ràng buộc

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits không có số 0 ở đầu, ngoại trừ chính số 0, được viết là [0].

Ví dụ

Đầu vào: digits = [4, 3, 9]
Đầu ra: [4, 4, 0]
Giải thích: Số đó là 439, và 439 + 1 = 440. Chữ số cuối cùng 9 chuyển thành 0 và chuyển số nhớ sang chữ số 3, khiến nó thành 4.

Đầu vào: digits = [0]
Đầu ra: [1]
Giải thích: Số 0 được viết là [0], và 0 + 1 = 1.

Câu hỏi mở rộng

Bạn sẽ trừ đi một như thế nào nếu số đó lớn hơn hoặc bằng 1? Khi nào kết quả mất chữ số đầu tiên, như trong [1, 0, 0]?

Lời giải

Một số có 100 chữ số vượt quá giới hạn của mọi số nguyên 64 bit, vốn đạt giá trị gần 1.8 × 10^19, nên bạn không thể chuyển đổi rồi cộng. Hãy cộng như cách bạn làm trên giấy, bắt đầu từ chữ số cuối cùng và nhớ sang hàng tiếp theo. Khi cộng 1, chỉ các chữ số 9 ở cuối thay đổi thành 0, cùng với chữ số ngay bên trái chúng.

Phép cộng có nhớ, từng chữ số một

Ý tưởng

Bắt đầu với số nhớ bằng 1, chính là số bạn đang cộng. Với mỗi chữ số, tính từ bên phải, tổng của cột là chữ số đó cộng với số nhớ: total % 10 được đưa vào kết quả và total / 10 là số nhớ tiếp theo. Tổng nhiều nhất là 9 + 1 = 10, nên số nhớ luôn là 0 hoặc 1. Nếu còn số nhớ sau chữ số đầu tiên, hãy thêm nó làm chữ số đầu mới, như trong phép tính 999 + 1 = 1000.

Bạn tạo chữ số cuối của kết quả trước, vì vậy hãy thu thập các chữ số theo thứ tự đó rồi đảo ngược chúng ở cuối. Cách này cần thời gian O(n) và một mảng mới có tối đa n + 1 chữ số.

Thuật toán

Đặt carry bằng 1 và tạo một danh sách trống để chứa đáp án.
Với mỗi chữ số, từ cuối đến đầu, tính total = digit + carry.
Thêm total % 10 vào đáp án và đặt carry bằng total / 10, làm tròn xuống.
Sau vòng lặp, nếu carry bằng 1, hãy thêm nó vào.
Đảo ngược đáp án rồi trả về.

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

Dừng ở chữ số đầu tiên nhỏ hơn 9

Ý tưởng

Một chữ số nhỏ hơn 9 hấp thụ số nhớ 1: chữ số đó tăng thêm một đơn vị và mọi chữ số ở bên trái giữ nguyên giá trị. Chỉ chữ số 9 mới truyền số nhớ đi tiếp bằng cách chuyển thành 0. Vì vậy, bạn có thể dừng ở chữ số đầu tiên nhỏ hơn 9 và trả về mảng đầu vào đã được thay đổi tại chỗ. Với [2, 9, 0, 9], chữ số 9 cuối cùng chuyển thành 0, chữ số 0 chuyển thành 1, rồi bạn trả về [2, 9, 1, 0] mà không cần đọc hai chữ số đầu tiên.

Nếu không có chữ số nào nhỏ hơn 9, số đó là 10^n - 1 và kết quả là số 1 theo sau bởi n số 0. Đây là trường hợp duy nhất cần một mảng mới, vì vậy trong những trường hợp khác, không gian bổ sung là O(1).

Thuật toán

Duyệt các chỉ số từ cuối về đầu.
Nếu chữ số nhỏ hơn 9, tăng chữ số đó lên một đơn vị rồi trả về mảng.
Nếu không, chữ số đó là 9: đặt nó thành 0 rồi dịch sang trái một vị trí.
Nếu vòng lặp kết thúc, mọi chữ số đều là 9: trả về số 1 theo sau là n số 0.

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

Lỗi thường gặp và trường hợp biên

Chuyển mảng thành số nguyên rồi chuyển ngược lại. Số nguyên 64 bit chứa tối đa 19 hoặc 20 chữ số, vì vậy 100 chữ số sẽ gây tràn số, còn số dấu phẩy động mất các chữ số cuối thậm chí sớm hơn.
Quên thêm chữ số. [9, 9, 9] phải trở thành [1, 0, 0, 0]; code chỉ viết lại các chữ số hiện có sẽ trả về [0, 0, 0].
Cộng 1 vào chữ số đầu tiên. Mảng được sắp xếp từ chữ số có giá trị lớn nhất đến nhỏ nhất, nên chữ số hàng đơn vị là phần tử cuối cùng.
Không trả về sau khi một chữ số nhỏ hơn 9 nhận phần nhớ. Khi đó, vòng lặp sẽ thay đổi những chữ số cần được giữ nguyên: [1, 9, 3] phải trở thành [1, 9, 4].
Trong Lua và R, mảng bắt đầu từ 1, nên chữ số cuối cùng nằm ở chỉ số n, không phải n - 1.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Plus One là gì?

Cả hai cách đều chạy trong thời gian O(n) với n chữ số, vì trường hợp toàn số 9 sẽ xử lý mọi chữ số. Phiên bản thoát sớm dừng sau các số 9 ở cuối và dùng thêm O(1) dung lượng, trừ khi đáp án cần thêm một chữ số ở đầu.

Tại sao không chuyển các chữ số thành số nguyên?

Số này có thể có 100 chữ số, còn số nguyên 64 bit chỉ đạt đến khoảng 1.8 × 10^19, tức là 20 chữ số. Python và Ruby có số nguyên không giới hạn, nên phép chuyển đổi hoạt động trong các ngôn ngữ đó, nhưng đoạn code này không áp dụng được cho các ngôn ngữ khác. Xử lý từng chữ số sẽ không bao giờ gây tràn số.

Làm thế nào để cộng hai số được lưu dưới dạng mảng chữ số?

Dùng phương pháp tính theo cột, với một chỉ số ở cuối mỗi mảng. Ở mỗi cột, cộng hai chữ số, coi chữ số còn thiếu là 0, rồi cộng thêm số nhớ. Dừng khi đã dùng hết cả hai mảng và số nhớ bằng 0, sau đó đảo ngược các chữ số đã thu thập.

def plusOne(digits):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

digits = [4, 3, 9]

Đầu ra mong đợi

[4, 4, 0]