Bài 9 Leetcode: Palindrome Number

Đề bài:

Cho một số nguyên x, trả về true nếu x là một palindrome (xuôi hay ngược đều giống nhau), và trả về false nếu ngược lại.

Ví dụ 1:

Input: x = 121
Output: true
Giải thích: Số 121 đọc từ trái sang phải và từ phải sang trái đều là 121.

Ví dụ 2:

Input: x = -121
Output: false
Giải thích: Từ trái sang phải, số -121 đọc là -121. Từ phải sang trái, nó trở thành 121-. Do đó, nó không phải là một palindrome.

Ví dụ 3:

Input: x = 10
Output: false
Giải thích: Đọc từ phải sang trái, số 10 trở thành 01. Do đó, nó không phải là một palindrome.

Ràng buộc:

  • -2^31 <= x <= 2^31 – 1

Giải thích thuật toán bằng C++

class Solution {
 public:
  bool isPalindrome(int x) {
    if (x < 0)
      return false;

    long reversed = 0;
    int y = x;

    while (y) {
      reversed = reversed * 10 + y % 10;
      y /= 10;
    }

    return reversed == x;
  }
};

Đây là một đoạn mã trong ngôn ngữ C++ để triển khai hàm isPalindrome(int x) theo thuật toán đã mô tả trước đó. Dưới đây là giải thích chi tiết về thuật toán này:

1. Hàm isPalindrome(int x): Đây là hàm chính để kiểm tra xem số nguyên x có phải là một palindrome hay không. Hàm này nhận đầu vào là một số nguyên x.

2. Kiểm tra x < 0: Nếu x là một số âm, hàm trả về false vì một số âm không thể là một palindrome.

3. Khởi tạo biến reversed với giá trị ban đầu là 0. Biến này sẽ lưu giữ giá trị số đảo ngược của x.

4. Khởi tạo biến y với giá trị ban đầu là x. Biến y sẽ được sử dụng trong quá trình tính toán.

5. Vòng lặp while: Trong vòng lặp này, ta tiếp tục thực hiện các bước sau cho đến khi y trở thành 0.

– Cập nhật giá trị của reversed bằng cách nhân reversed với 10 và cộng với phần dư của y khi chia cho 10 (y % 10). Điều này cho phép ta xây dựng dần giá trị số đảo ngược của x.

– Chia y cho 10 để tiến tới phần kế tiếp của x trong quá trình lặp.

6. Kiểm tra giá trị reversed và x: Cuối cùng, ta kiểm tra nếu giá trị của reversed bằng x, tức là số đảo ngược của x giống với x ban đầu, thì trả về true. Ngược lại, trả về false.

Thuật toán này hoạt động bằng cách xây dựng số đảo ngược của x và so sánh nó với x ban đầu để xác định xem x có phải là một palindrome hay không.

Giải thích thuật toán bằng Java

class Solution {
  public boolean isPalindrome(int x) {
    if (x < 0)
      return false;

    long reversed = 0;
    int y = x;

    while (y > 0) {
      reversed = reversed * 10 + y % 10;
      y /= 10;
    }

    return reversed == x;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def isPalindrome(self, x: int) -> bool:
    if x < 0:
      return False

    rev = 0
    y = x

    while y:
      rev = rev * 10 + y % 10
      y //= 10

    return rev == x

 

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.