Palindrome Number (Easy)

Bài toán

Mở đầu với chuỗi bài về lập trình thuật toán chúng tôi xin giới thiệu bài toán Palindrome-Number

https://leetcode.com/problems/palindrome-number/

Tôi xin tóm tắt lại bài toán như sau:

Bài toán cho một số nguyên x hãy viết chương trình để kiểm tra xem nó có phải số Palindrome không (số Palindrome là số mà đọc từ trái sang phải hay phải sang trái thì nó vẫn giống nhau hay nói cách khác nó bằng với đảo ngược của nó). Chú ý số nguyên thì có thể là số âm hoặc dương.

Ví dụ:

Example 1:

Input: x = 121
Output: true

Example 2:

Input: x = -121
Output: false

Example 3:

Input: x = 10
Output: false

Hướng giải quyết

Nhận xét

• Số âm thì không thể là số Palindrome
• Nếu là số dương thì chỉ cần so sánh nó và số đảo ngược của nó
• Để tìm số đảo ngược thì mình sẽ dùng phép toán chia lấy phần nguyên và chia lấy phần dư. Ví dụ 123 chia lấy nguyên với 10 được 12 còn 123 chia lấy dư với 10 thì được 3.Trong python thì “%” là được dùng để chia lấy phần dư, còn “//” được dùng để chia lấy phần nguyên.

a = 123
b = 10
print(a % b)  # kết quả ra 3
print(a // b)  # kết quả ra 12

Giải pháp

• Bước 1 : Kiểm tra xem x có phải là số âm không. Nếu là số âm thì trả kết quả ra false

• Bước 2 : Đi tìm số đảo ngược của x. Sử dụng phép chia lấy nguyên và phép chia lấy dư để tìm số đảo ngược của x bằng các bước sau :

  1. Khởi tạo biến reverse_number = 0, và y=x
  2. Lặp lại đến khi số y còn khác 0: a. Lấy số dư của y khi chia cho 10 bằng phép chia lấy dư (y **% 10**) và lưu vào biến k . b. Cập nhật giá trị của y bằng phép chia lấy nguyên (y **// 10**). c. Cập nhật giá trị của reverse_number bằng cách nhân nó với 10 và cộng với k.
  3. Trả về reverse_number.

  Chạy thử với y = 123:

  Bước 1 : reverse_number = 0;

  Bước 2 :

  • y = 123 ≠ 0
  • k = 123 % 10 = 3; y = 123 // 10 = 12; reverse_number=0*10 + 3 = 3;
  • y = 12 ≠ 0
  • k = 12 % 10 = 2; y = 12 // 10 = 1; reverse_number=3*10 + 2 = 32;
  • y = 1 ≠ 0
  • k = 1 % 10 = 1; y = 1 // 10 = 0; reverse_number = 32*10 + 1 = 321
  • y = 0 ⇒ Kết thúc bước 2

  Bước 3 : Trả về reverse_number=321

• Bước 3: Kiểm tra reverse_number với x ban đầu :

  • Nếu reverse_number = x ⇒ trả về True
  • Nếu reverse_number ≠ x ⇒ trả về False

Python Code

class Solution:
    def getReverse(self, y: int) -> int:
        reverse_number = 0
        while y != 0:
            k = y % 10
            y //= 10
            reverse_number = reverse_number * 10 + k
        return reverse_number

    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        y = x
        reverse_number = self.getReverse(y)
        return reverse_number == x

Link nộp bài : https://leetcode.com/problems/palindrome-number/