Add Two Numbers
Bạn nhận được hai số nguyên không âm, mỗi số được lưu dưới dạng danh sách liên kết đơn gồm các chữ số, với chữ số có giá trị nhỏ nhất đứng trước. Trong danh sách thứ nhất, nút i chứa chữ số values1[i] và liên kết đến nút next1[i]. Danh sách thứ hai hoạt động tương tự, với next2 và values2. Trong cả hai danh sách, -1 đánh dấu kết thúc danh sách và nút đầu là nút 0. Các nút không được lưu theo thứ tự trong danh sách, vì vậy hãy lần theo các liên kết.
Trả về các chữ số của tổng hai số, với chữ số có giá trị nhỏ nhất đứng trước.
Hàm
- next1integer-array
- chỉ số của nút mà mỗi nút của số thứ nhất liên kết đến, hoặc -1 nếu đó là nút cuối cùng
- values1integer-array
- chữ số mà mỗi nút của số thứ nhất lưu giữ
- next2integer-array
- chỉ số của nút mà mỗi nút của số thứ hai liên kết đến, hoặc -1 nếu đó là nút cuối cùng
- values2integer-array
- chữ số được lưu trong mỗi nút của số thứ hai
- Trả vềinteger-array
- các chữ số của tổng, bắt đầu từ chữ số hàng thấp nhất
Ràng buộc
1 ≤ L1 ≤ 100, trong đóL1là độ dài củanext1vàvalues1.1 ≤ L2 ≤ 100, trong đóL2là độ dài củanext2vàvalues2.0 ≤ values1[i], values2[j] ≤ 9- Mỗi phần tử của
next1là-1hoặc chỉ số nút trong danh sách thứ nhất, và mỗi phần tử củanext2là-1hoặc chỉ số nút trong danh sách thứ hai. - Bắt đầu tại nút
0, mỗi danh sách đi qua tất cả các nút đúng một lần rồi đến-1. Không có chu trình. - Không có số nào bắt đầu bằng số 0: nút cuối cùng của một danh sách chứa chữ số khác
0, trừ khi danh sách chỉ có chữ số0.
Ví dụ
- Đầu vào
- next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
- Đầu ra
- [5, 4, 1, 1]
- Giải thích
- Danh sách đầu tiên duyệt qua các nút
0, 2, 1và đọc được8, 1, 6, tạo thành số 618. Danh sách thứ hai đọc được7, 2, 5, tạo thành số 527. Tổng của chúng là 1145, vậy đáp án là5, 4, 1, 1.
- Đầu vào
- next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
- Đầu ra
- [0, 0, 0, 0, 1]
- Giải thích
- Danh sách thứ hai biểu thị số 9991:
1, 9, 9, 9. Cộng thêm 9 sẽ được 10000: mỗi cột tạo ra một0và một số nhớ, số nhớ cuối cùng trở thành chữ số thứ năm.
- Đầu vào
- next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
- Đầu ra
- [7, 5]
- Giải thích
- Số đầu tiên là 0 và danh sách thứ hai đọc là
7, 5, tức số 57. Cộng thêm 0 không làm thay đổi gì, nên đáp án là[7, 5].
Câu hỏi mở rộng
Bạn sẽ cộng các số như thế nào nếu danh sách lưu chữ số có giá trị lớn nhất ở đầu?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Chuyển từng danh sách thành một số sẽ không được: 100 chữ số không thể vừa với bất kỳ kiểu số nguyên nào. Bạn cộng hai số dài trên giấy như thế nào?
Các danh sách bắt đầu từ hàng đơn vị, đúng vị trí bắt đầu khi cộng theo cột. Mỗi cột cộng một chữ số của mỗi số với số nhớ từ cột trước. Cột ghi
sum % 10và chuyển phần nhớsum / 10, làm tròn xuống.Duyệt đồng thời cả hai danh sách, mỗi danh sách dùng một con trỏ. Khi một danh sách đã hết phần tử, hãy cộng thêm
0. Tiếp tục khi một trong hai con trỏ khác-1hoặc số nhớ bằng1, để số nhớ cuối cùng trở thành một chữ số nữa.
Lời giải
Các số này quá dài để lưu bằng bất kỳ kiểu số nguyên nào, nên hãy cộng chúng như trên giấy: cộng từng cột, nhớ 1 khi tổng một cột đạt 10. Các danh sách lưu chữ số hàng đơn vị trước, nên khi duyệt qua chúng, bạn sẽ lần lượt gặp các cột theo thứ tự cần cộng.
Sao chép các chữ số ra, rồi cộng từng cột
Ý tưởng
Con trỏ ở đây là chỉ số nút, còn tiến lên nghĩa là node = next[node]. Sao chép các chữ số của mỗi danh sách vào một mảng, để chỉ số i chứa chữ số có giá trị 10^i: [8, 1, 6] và [7, 2, 5] trong ví dụ đầu tiên.
Sau đó cộng như trên giấy, xem chữ số còn thiếu là 0. Ở mỗi cột, ghi sum % 10 rồi nhớ phần còn lại: 8 + 7 = 15 ghi 5 và nhớ 1, 1 + 2 + 1 = 4, còn 6 + 5 = 11 ghi 1. Số nhớ cuối cùng trở thành chữ số cuối: [5, 4, 1, 1].
Việc sao chép tốn thêm bộ nhớ O(L1 + L2), dù phép cộng không cần đến.
Thuật toán
- Duyệt từng danh sách từ nút
0và chép các chữ số vào một mảng. - Đặt
carry = 0. Với mỗi chỉ sốicho đến độ dài của mảng dài hơn, cộng các chữ số ở vị tríinếu có cùng với số nhớ. - Thêm
sum % 10và đặtcarrybằngsum / 10, làm tròn xuống. - Nếu số nhớ bằng
1sau cột cuối cùng, hãy thêm nó.
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 resultDuyệt đồng thời cả hai danh sách và nhớ giá trị nhớ
Ý tưởng
Cột i chỉ dùng nút thứ i của mỗi danh sách, vì vậy hãy giữ một con trỏ cho mỗi danh sách, a và b, rồi di chuyển cả hai khi chuyển qua các cột.
Một vòng lặp chạy khi a khác -1, hoặc b khác -1, hoặc số nhớ là 1. Con trỏ vẫn còn nút sẽ cộng chữ số của nút đó rồi tiến lên; con trỏ ở -1 thì không cộng gì. Cách này xử lý các số có độ dài khác nhau mà không cần vòng lặp thứ hai, còn điều kiện số nhớ sẽ ghi thêm chữ số ở cuối.
Trong ví dụ thứ hai, 9 cộng 9991, tổng của mỗi cột đều bằng 10 và ghi 0. Sau bốn cột, cả hai danh sách đều đã hết, nhưng số nhớ là 1, nên vòng lặp chạy thêm một lần nữa: [0, 0, 0, 0, 1]. Ngoài đáp án, cách này dùng ba số nguyên.
Thuật toán
- Đặt
a = 0,b = 0vàcarry = 0. - Trong khi
a != -1hoặcb != -1hoặccarry > 0, bắt đầu tổng của cột bằngcarry. - Nếu
a != -1, cộngvalues1[a]rồi đặta = next1[a]. Làm tương tự vớibtrong danh sách thứ hai. - Thêm
sum % 10vào danh sách rồi đặtcarrybằngsum / 10, làm tròn xuống. - Trả về các chữ số bạn đã thêm vào danh sách.
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
Lỗi thường gặp và trường hợp biên
- Chuyển mỗi danh sách thành số nguyên rồi cộng lại. Một số có 100 chữ số vượt quá giới hạn của mọi kiểu dữ liệu 64 bit.
- Bỏ qua số nhớ cuối cùng. Vòng lặp dừng khi cả hai danh sách kết thúc sẽ trả về
[0, 0, 0, 0]ở ví dụ thứ hai. - Dừng khi danh sách ngắn hơn kết thúc. Khi đó, ví dụ thứ hai sẽ làm mất ba số 9 của 9991 và số nhớ truyền qua chúng.
- Đọc các chữ số theo thứ tự trong mảng. Ở ví dụ thứ nhất,
values1là[8, 6, 1], nhưng số đó là 618 khi đọc theo các liên kết. - Quên tính độ lệch trong Lua và R, nơi mảng bắt đầu từ 1. Giữ chỉ số nút bắt đầu từ 0 và đọc
next1[node + 1].
Câu hỏi thường gặp3
Vì sao các chữ số được lưu theo thứ tự ngược trong bài Cộng hai số?
Phép cộng bắt đầu từ chữ số hàng đơn vị, còn danh sách liên kết đơn chỉ có thể được duyệt từ đầu danh sách. Khi chữ số có giá trị nhỏ nhất đứng trước, ta duyệt các cột theo đúng thứ tự cộng, nên số nhớ tiến về phía trước cùng các con trỏ.
Độ phức tạp thời gian khi cộng hai số được lưu dưới dạng danh sách liên kết là bao nhiêu?
Độ phức tạp là O(max(L1, L2)): mỗi cột cần một bước, cộng thêm một bước nếu còn số nhớ ở cuối. Ngoài đáp án, phiên bản duyệt một lượt dùng bộ nhớ O(1): hai con trỏ và số nhớ.
Giá trị nhớ có thể lớn hơn 1 không?
Không. Một cột cộng hai chữ số có giá trị tối đa là 9 với số nhớ tối đa là 1, nên tổng tối đa là 19. Chia cho 10 rồi làm tròn xuống sẽ được 0 hoặc 1.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def addTwoNumbers(next1, values1, next2, values2):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
next1 = [2, -1, 1] values1 = [8, 6, 1] next2 = [2, -1, 1] values2 = [7, 5, 2]
Đầu ra mong đợi
[5, 4, 1, 1]