9. Palindrome Number

Easy

Description

判斷一個整數 x 是否為回文數。回文數是指正著讀和反著讀都一樣的數。負數不是回文數。

Example:

Input: x = 121 Output: true

Intuition#

核心思路：反轉後半段數字並與前半段比較，避免整數溢位且只需 O(log n) 時間。

負數一定不是回文，以 0 結尾的數（除了 0 本身）也不是
將數字轉成字串再比較是最簡單的方法，但題目要求不轉字串
只反轉一半數字：當反轉部分 >= 剩餘部分時停止，比較兩者是否相等

Approaches#

1: 完全反轉數字#

概念: 反轉整個數字，比較是否與原數相等
時間複雜度: O(log n) - 數字位數
空間複雜度: O(1)

class Solution {
    fun isPalindrome(x: Int): Boolean {
        if (x < 0) return false
        var original = x
        var reversed = 0L
        var num = x
        while (num > 0) {
            reversed = reversed * 10 + num % 10
            num /= 10
        }
        return original.toLong() == reversed
    }
}

⭐2: 反轉一半數字#

概念: 只反轉後半段數字，與前半段比較。當反轉數 >= 剩餘數時停止
時間複雜度: O(log n)
空間複雜度: O(1)

class Solution {
    fun isPalindrome(x: Int): Boolean {
        // 負數或以 0 結尾（非 0）都不是回文
        if (x < 0 || (x % 10 == 0 && x != 0)) return false

        var num = x
        var reversed = 0
        while (num > reversed) {
            reversed = reversed * 10 + num % 10
            num /= 10
        }

        // 偶數位：num == reversed
        // 奇數位：num == reversed / 10（中間那位不影響）
        return num == reversed || num == reversed / 10
    }
}

🔑 Takeaways#

Pattern: 反轉一半數字——避免溢位且效率更高
關鍵技巧: 迴圈終止條件 num > reversed 巧妙地表示「處理到一半」，奇數位時用 reversed / 10 去掉中間位