Tóm tắt: Cho 2 số nguyên được biểu diễn bằng LinkedList, hãy tính tổng của 2 số và trả lại kết quả cũng là LinkedList.
Ví dụ:
l1 = 7 → 2 → 4 → 3
l2 = 5 → 6 → 4
Tổng của hai số là 7243 + 564 = 7807
Biểu diễn bằng LinkedList: 7 → 8 → 0 → 7
(by phucnh)
Đây là một bài áp dụng cách chia 2 số nguyên. Ta cùng ôn lại cách chia.
Giả sử ta có phân số 4/9, tử số (numerator) là 4, phân số (denominator) là 9, để biểu diễn phân số dưới dạng số thực, ta thực hiện 4 chia 9 như sau:
- Phần nguyên = tử số / mẫu số - 4 / 9 = 0, dư 4
- Phần thập phân = số dư * 10 / mẫu số
4 * 10 / 9 = 4, ta có kết quả = 0.4, dư 4
4 * 10 / 9 = 4, ta có kết quả = 0.44, dư 4
4 * 10 / 9 = 4, ta có kết quả = 0.444, dư 4
…
Nếu ta cứ tiếp tục thực hiện phép chia, ta luôn luôn thu được số dư là 4, và phần thập phân là một chuỗi số 4 vô hạn. Theo đề bài, ta cần biểu diễn dưới dạng “0.(4)”.
Bạn đọc có thể thực hiện tương tự để biểu diễn các phân số 1/3, 2/3, 4/333…
Ta nhận thấy, nếu ta gặp số dư lặp lại, ta sẽ được kết quả chia giống với kết quả chia trước đó, và độ dài của số thập phân là vô hạn. Như vậy ta hoàn toàn có thể sử dụng hashmap để kiểm tra xem đã gặp số dư trước đó chưa. Thuật toán được thực hiện như sau:
https://pastebin.com/ucpPX8T2
