[Leetcode] 9. Palindrome Number

9. Palindrome Number

• Hardness: $\color{green}\textsf{Easy}$
• Ralated Topics: Math

一、題目

Given an integer x, return true if x is palindrome number.
An integer is a palindrome when it reads the same backward as forward.

• For example, 121 is a palindrome while 123 is not.

Example 1:

• Input: x = 121
• Output: true
• Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

• Input: x = -121
• Output: false
• Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

• Input: x = 10
• Output: false
• Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

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

Follow up: Could you solve it without converting the integer to a string?

二、分析

• 若直接將數字轉換成 string，即可當作 palindrome string 的題目來處理，但題目在 follow up 規定不可以轉成 string，那我們可以嘗試用翻轉數字的方式來解題。
  • 注意此處我們讓 rev <= x 時為終止條件

  while (x > rev) {
      rev = 10 * rev + x % 10;
      x /= 10;
  }

• 觀察可得
  • x < 0 必非 palindrome
  • x < 10 必為 palindrome
  • x % 10 == 0 必非 palindrome
• 翻轉數字時，注意數字長可能為奇數或偶數，故
  • 當偶數長時，翻轉到等長時，rev == x 時為 palindrome。
  • 當奇數長時，翻轉到 rev 比 x 多一位時，若 rev/10 == x 時為 palindrome。
• 時間複雜度 $O(n)$，$n$ 為 10 的冪次的絕對值，故 $O(n)=O(31)=O(1)$。

三、解題

1. Math

• Time complexity: $O(1)$
• Space complexity: $O(1)$

bool isPalindrome(int x) {
    if (x < 0) return false;
    if (x < 10) return true;
    if (x % 10 == 0) return false;
    
    int rev = 0;
    while (x > rev) {
        rev = 10 * rev + x % 10;
        x /= 10;
    }
    return rev == x || rev/10 == x;
}

回目錄 Catalog