[LeetCode解題攻略] 9. Palindrome Number

這篇文章將介紹 LeetCode 題目 9. Palindrome Number，這是一道簡單但經典的數字題，目標是判斷給定的整數是否為回文數。這道題目可以幫助我們理解數字操作以及回文判斷的基礎邏輯。

題目概述

給定一個整數 x，判斷其是否為回文數。回文數指的是正向和反向讀取均相同的數字。

範例：

Input: x = 121
Output: true

Input: x = -121
Output: false

Input: x = 10
Output: false

思路分析

此題的核心在於如何高效地判斷數字是否為回文數。我們可以用數學操作或者將數字轉為字串來實現這個檢查。

考慮到以下幾個重要的邊界條件：

1. 負數永遠不會是回文數，因為它們的第一個字符是 -。
2. 任何以 0 結尾的數字（除了 0 本身）都不會是回文數，例如 10 不是回文數。

解法一：反轉數字的後半段

一種優化解法是反轉數字的後半部分，並與前半部分進行比較。這樣可以減少反轉整個數字所需的計算量。

步驟

1. 如果數字為負數或以 0 結尾但不為 0，則直接返回 false。
2. 初始化一個變數 reversed_half 用於儲存反轉後的一半數字。
3. 當 x 大於 reversed_half 時，取出 x 的最後一位並添加到 reversed_half 中，逐步反轉後半部分。
4. 最後，判斷 x == reversed_half 或 x == reversed_half // 10 是否成立。若成立，則為回文數。

實作 (Python)

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False
        
        reversed_half = 0
        while x > reversed_half:
            reversed_half = reversed_half * 10 + x % 10
            x //= 10
        
        return x == reversed_half or x == reversed_half // 10

複雜度分析

• 時間複雜度：O(log(x))，因為我們僅反轉數字的一半。
• 空間複雜度：O(1)，因為僅使用了固定數量的變數。

解法二：字串轉換法

如果不介意空間複雜度，可以將數字轉為字串，這樣比較簡潔，但效率較低。

步驟

1. 若數字為負，直接返回 false。
2. 將數字轉為字串。
3. 判斷字串正向和反向是否相同，若相同則為回文數。

實作 (Python)

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]

複雜度分析

• 時間複雜度：O(n)，n 為數字的位數，需遍歷一半的字串進行比較。
• 空間複雜度：O(n)，因為字串反轉需要額外的空間。

這種方法簡單直觀，但在高效性上略遜於數字操作法。

總結

這道題目提供了理解數字處理和邏輯判斷的良好練習。總結解法：

• 數字反轉法：最優化的解法，僅反轉一半數字，高效且無需額外空間。
• 字串反轉法：簡潔但不夠高效。

希望這篇教學能幫助你掌握 Palindrome Number 題目的不同解法！