這篇文章將介紹 LeetCode 題目 9. Palindrome Number，這是一道簡單但經典的數字題，目標是判斷給定的整數是否為回文數。這道題目可以幫助我們理解數字操作以及回文判斷的基礎邏輯。
題目概述
給定一個整數 x，判斷其是否為回文數。回文數指的是正向和反向讀取均相同的數字。
Input: x = 121
Output: true
Input: x = -121
Output: false
Input: x = 10
Output: false
思路分析
此題的核心在於如何高效地判斷數字是否為回文數。我們可以用數學操作或者將數字轉為字串來實現這個檢查。
考慮到以下幾個重要的邊界條件：
- 負數永遠不會是回文數，因為它們的第一個字符是
-。 - 任何以 0 結尾的數字（除了 0 本身）都不會是回文數，例如
10不是回文數。
解法一：反轉數字的後半段
一種優化解法是反轉數字的後半部分，並與前半部分進行比較。這樣可以減少反轉整個數字所需的計算量。
步驟
- 如果數字為負數或以 0 結尾但不為 0，則直接返回
false。 - 初始化一個變數
reversed_half用於儲存反轉後的一半數字。 - 當
x大於reversed_half時，取出x的最後一位並添加到reversed_half中，逐步反轉後半部分。 - 最後，判斷
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)，因為僅使用了固定數量的變數。
解法二：字串轉換法
如果不介意空間複雜度，可以將數字轉為字串，這樣比較簡潔，但效率較低。
步驟
- 若數字為負，直接返回
false。 - 將數字轉為字串。
- 判斷字串正向和反向是否相同，若相同則為回文數。
實作 (Python)
class Solution:
def isPalindrome(self, x: int) -> bool:
return str(x) == str(x)[::-1]
複雜度分析
- 時間複雜度：O(n)，
n為數字的位數，需遍歷一半的字串進行比較。 - 空間複雜度：O(n)，因為字串反轉需要額外的空間。
這種方法簡單直觀，但在高效性上略遜於數字操作法。
總結
這道題目提供了理解數字處理和邏輯判斷的良好練習。總結解法：
- 數字反轉法：最優化的解法，僅反轉一半數字，高效且無需額外空間。
- 字串反轉法：簡潔但不夠高效。
希望這篇教學能幫助你掌握 Palindrome Number 題目的不同解法！
