Palindrome Number

Q: Số âm có phải là số đối xứng không?

Không. Khi đọc ngược, -121 trở thành 121- , và dấu trừ không có ký tự tương ứng ở đầu kia. Vì vậy, mọi số nguyên âm đều trả về false .

Q: Độ phức tạp thời gian của bài toán số đối xứng là gì?

Cả hai cách đều chạy trong thời gian O(log x) , vì số x có khoảng log10(x) chữ số và mỗi chữ số được xử lý một lần. Cách dùng chuỗi cần thêm O(log x) bộ nhớ cho phần văn bản; cách đảo ngược một nửa cần O(1) .

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

+10

Một số là số đối xứng nếu các chữ số của nó đọc từ trái sang phải và từ phải sang trái đều giống nhau, chẳng hạn như 1221. Với số nguyên x, hãy trả về true nếu đó là số đối xứng và false nếu không. Số âm không bao giờ được tính là số đối xứng vì dấu trừ của nó không có dấu tương ứng ở đầu kia.

Hàm

isPalindrome(x: integer) → boolean

xinteger: số nguyên cần kiểm tra, có thể là số âm
Trả vềboolean: true nếu x đọc giống nhau theo cả hai hướng, false nếu không

Ràng buộc

-2³¹ ≤ x ≤ 2³¹-1
Mọi số âm đều trả về false.

Ví dụ

Đầu vào: x = 121
Đầu ra: true
Giải thích: Đọc ngược lại, 121 vẫn là 121, nên đáp án là true.

Đầu vào: x = -121
Đầu ra: false
Giải thích: Khi đọc ngược, -121 trở thành 121-, đây là văn bản khác, nên đáp án là false.

Câu hỏi mở rộng

Bạn có thể giải bài này mà không chuyển số nguyên thành chuỗi không?

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

Một số là số đối xứng khi nó bằng chính số đảo ngược của nó. Nếu biểu diễn dưới dạng văn bản, bạn chỉ cần so sánh một lần. Nếu không dùng văn bản, việc dựng lại toàn bộ số đảo ngược có thể gây tràn số, vì vậy chỉ đảo ngược nửa sau của các chữ số rồi so sánh với nửa đầu.

So sánh chuỗi với phiên bản đảo ngược của nó

Ý tưởng

Viết số đó thành văn bản rồi so sánh với phiên bản đảo ngược của nó. Số âm không cần xử lý riêng: -121 bắt đầu bằng dấu trừ và kết thúc bằng một chữ số, nên không bao giờ bằng phiên bản đảo ngược 121-.

Văn bản có một ký tự cho mỗi chữ số, khoảng log10(x) ký tự và tối đa 11 ký tự trong trường hợp này. Cái giá phải trả là cần thêm một chuỗi.

Thuật toán

Chuyển x thành chuỗi s.
Đảo ngược s.
Trả về việc s có bằng chuỗi đảo ngược của nó hay không.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

Đảo ngược một nửa số

Ý tưởng

x % 10 cho chữ số cuối cùng, còn phép chia nguyên cho 10 loại bỏ chữ số đó. Chuyển các chữ số từ cuối x sang số thứ hai half sẽ tạo thành số đảo ngược từ những chữ số bạn đã loại bỏ. Dừng khi half lớn hơn hoặc bằng phần còn lại của x: bạn đã lấy một nửa số chữ số. 1221 kết thúc với x = 12 và half = 12, đây là một số đối xứng. Với số có số chữ số lẻ, half cũng chứa chữ số ở giữa: 12321 kết thúc với x = 12 và half = 123, vì vậy bạn so sánh x với half / 10.

Xử lý hai trường hợp trước vòng lặp. Số âm không bao giờ là số đối xứng. Số kết thúc bằng 0 phải bắt đầu bằng 0, điều chỉ xảy ra với số 0; nếu không kiểm tra trường hợp này, 10 kết thúc với x = 0 và half = 1, khiến x == half / 10 cho kết quả đúng do nhầm lẫn. half không bao giờ vượt quá 6 chữ số, nên vừa với mọi kiểu số nguyên.

Thuật toán

Nếu x là số âm, hoặc tận cùng là 0 và không bằng 0, hãy trả về false.
Đặt half = 0.
Khi x > half, đặt half = half * 10 + x % 10 rồi chia x cho 10 bằng phép chia lấy phần nguyên.
Trả về true nếu x == half (số chữ số chẵn) hoặc x == half / 10 (số chữ số lẻ).

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

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

Quên kiểm tra số âm. Trong các ngôn ngữ mà phép chia lấy phần dư giữ nguyên dấu, đảo ngược -121 sẽ cho kết quả -121 và phép kiểm tra vẫn đạt. Trong Python, vì -1 // 10 là -1, vòng lặp while x != 0 không bao giờ kết thúc.
Không loại bỏ các số kết thúc bằng 0. Khi đó, phép đảo ngược một nửa chấp nhận 10. Bản thân 0 là một số đối xứng.
Đảo ngược toàn bộ số trong số nguyên 32 bit. Số đảo ngược của 2147483647 không thể biểu diễn được.
Dùng / trong ngôn ngữ thực hiện phép chia cho kết quả dạng phân số. Hãy dùng Math.floor(x / 10) trong JavaScript, // trong Python, %/% trong R và ~/ trong Dart.
So sánh số đảo ngược hoàn chỉnh với x sau khi vòng lặp đã thay đổi x. Hãy giữ một bản sao của giá trị ban đầu.

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

Số âm có phải là số đối xứng không?

Không. Khi đọc ngược, -121 trở thành 121-, và dấu trừ không có ký tự tương ứng ở đầu kia. Vì vậy, mọi số nguyên âm đều trả về false.

Tại sao chỉ đảo ngược một nửa số?

Đảo ngược mọi chữ số có thể khiến số nguyên 32 bit bị tràn: số đảo ngược của 2147483647 lớn hơn giá trị int lớn nhất. Một nửa số chữ số luôn vừa, và vòng lặp chỉ cần thực hiện một nửa công việc.

Độ phức tạp thời gian của bài toán số đối xứng là gì?

Cả hai cách đều chạy trong thời gian O(log x), vì số x có khoảng log10(x) chữ số và mỗi chữ số được xử lý một lần. Cách dùng chuỗi cần thêm O(log x) bộ nhớ cho phần văn bản; cách đảo ngược một nửa cần O(1).

def isPalindrome(x):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

x = 121

Đầu ra mong đợi

true