Reverse the Digits

Q: Đảo ngược một số nguyên có thể gây tràn số không?

Đúng, nếu đầu vào có thể là bất kỳ số nguyên 32 bit nào: 1000000009 vừa, nhưng số đảo ngược của nó 9000000001 thì không. Ở đây, n nhỏ hơn 10^9 , nên số đảo ngược có nhiều nhất 9 chữ số và luôn vừa.

Người mớiToán và mô phỏng

+10

Bạn nhận được một số nguyên không âm n. Hãy trả về số tạo thành bằng cách viết các chữ số thập phân của nó theo thứ tự ngược lại. Các số 0 nằm ở đầu sẽ bị bỏ đi, vì vậy 120 trở thành 21.

Hàm

reverseDigits(n: integer) → integer

ninteger: số nguyên không âm cần đảo ngược
Trả vềinteger: các chữ số của n theo thứ tự ngược lại, dưới dạng một số

Ràng buộc

0 ≤ n < 10⁹
Số đảo ngược cũng nằm trong phạm vi số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: n = 1234
Đầu ra: 4321
Giải thích: Các chữ số của 1234 là 1, 2, 3 và 4. Đọc từ cuối lên, chúng là 4, 3, 2 và 1, tức là 4321.

Đầu vào: n = 120
Đầu ra: 21
Giải thích: Đọc ngược lại, 120 cho các chữ số 0, 2 và 1. Số 0 ở đầu không được tính trong một số, nên đáp án là 21.

Đầu vào: n = 0
Đầu ra: 0
Giải thích: 0 có một chữ số, và đảo ngược nó vẫn cho ra 0.

Câu hỏi mở rộng

Nếu n có thể là bất kỳ số nguyên 32 bit nào, số đảo ngược của nó có thể không vừa. Làm thế nào bạn phát hiện điều đó trước khi phép nhân gây tràn?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Đảo ngược chuỗi thập phân chỉ cần một dòng trong hầu hết các ngôn ngữ và là câu trả lời đầu tiên khá ổn. Sau đó, người phỏng vấn thường yêu cầu tạo kết quả tương tự mà không dùng chuỗi. Cách làm bằng số học dựa trên hai phép toán: n % 10 lấy chữ số cuối cùng và n / 10 (phép chia lấy phần nguyên) loại bỏ chữ số đó.

Đảo ngược chuỗi thập phân

Ý tưởng

Các chữ số của một số là các ký tự trong cách viết thập phân của số đó. Chuyển n thành văn bản, đảo ngược các ký tự rồi phân tích kết quả: 1234 thành "1234", rồi "4321", sau đó là 4321. Các số 0 ở đầu tự được xử lý, vì phân tích "021" cho kết quả 21.

Cả khối lượng công việc lẫn văn bản đều tăng theo số chữ số, O(log n), tối đa là 9 chữ số ở đây.

Thuật toán

Chuyển n thành chuỗi thập phân.
Đảo ngược các ký tự.
Phân tích chuỗi đã đảo ngược thành số nguyên rồi trả về số đó.

def reverseDigits(n):
    # int() ignores the leading zeros that trailing zeros turn into.
    return int(str(n)[::-1])

Đẩy và lấy chữ số bằng phép tính số học

Ý tưởng

Lấy từng chữ số ở cuối n rồi thêm vào cuối result: result * 10 + d dịch các chữ số hiện có sang trái một vị trí và đặt d vào hàng đơn vị. Với 1234, result lần lượt thành 4, 43, 432, 4321, còn n lần lượt thành 123, 12, 1, 0. Vòng lặp chạy một lần cho mỗi chữ số.

Không bao giờ xuất hiện số 0 ở đầu: với 120, chữ số đầu tiên được lấy là 0, và 0 * 10 + 0 vẫn bằng 0. Với n = 0, vòng lặp không chạy và kết quả là 0. Chỉ giữ lại hai số nguyên, nên dung lượng bộ nhớ phụ là O(1).

Thuật toán

Đặt result = 0.
Khi n lớn hơn 0, hãy tính chữ số cuối cùng bằng n % 10.
Đặt result = result * 10 + digit.
Bỏ chữ số đó bằng cách dùng phép chia nguyên để tính n = n / 10.
Trả về result.

def reverseDigits(n):
    result = 0
    while n > 0:
        result = result * 10 + n % 10  # push the last digit of n
        n //= 10                        # drop it from n
    return result

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

Dùng phép chia thông thường khi cần phép chia lấy phần nguyên. Trong JavaScript, Python 3 và Lua, n / 10 cho kết quả 123.4, vì vậy n không bao giờ trở lại thành số nguyên và result chứa các phần thập phân. Hãy dùng Math.floor, // hoặc phép chia lấy phần nguyên của ngôn ngữ bạn đang dùng.
Viết vòng lặp thành while n >= 10. Vòng lặp dừng trước chữ số cuối cùng, nên 1234 trở thành 432.
Trả về văn bản đã đảo ngược mà không phân tích nó thành số. "021" không phải là số 21, nên phép so sánh với đáp án mong đợi sẽ thất bại.
Định dạng số thực double trong R bằng as.character. Khi n được lưu dưới dạng số thực double, nó in 100000000 thành 1e+08, và văn bản đảo ngược là 80+e1. Hãy dùng format(n, scientific = FALSE).

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

Các số 0 ở cuối sẽ thế nào khi bạn đảo ngược một số?

Chúng sẽ trở thành các số 0 đứng đầu, vốn không có trong một số, nên chúng biến mất. Đảo ngược 120 cho kết quả 21, còn đảo ngược 100000000 cho kết quả 1. Vòng lặp số học tự loại bỏ chúng, vì cộng 0 vào kết quả rỗng vẫn cho ra 0.

Độ phức tạp thời gian của việc đảo ngược một số nguyên là gì?

Vòng lặp (loop) chạy một lần cho mỗi chữ số thập phân, và số n có khoảng log10(n) + 1 chữ số, nên thời gian chạy là O(log n). Phiên bản số học dùng O(1) bộ nhớ bổ sung; phiên bản chuỗi (string) lưu các chữ số dưới dạng văn bản, nên cần O(log n) bộ nhớ.

Đảo ngược một số nguyên có thể gây tràn số không?

Đúng, nếu đầu vào có thể là bất kỳ số nguyên 32 bit nào: 1000000009 vừa, nhưng số đảo ngược của nó 9000000001 thì không. Ở đây, n nhỏ hơn 10^9, nên số đảo ngược có nhiều nhất 9 chữ số và luôn vừa.

def reverseDigits(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 1234

Đầu ra mong đợi