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