判斷一個整數
x是否為回文數。回文數是指正著讀和反著讀都一樣的數。負數不是回文數。
Example:
Input: x = 121 Output: true
Intuition
TIP
核心思路：反轉後半段數字並與前半段比較，避免整數溢位且只需 O(log n) 時間。
- 負數一定不是回文，以 0 結尾的數（除了 0 本身）也不是
- 將數字轉成字串再比較是最簡單的方法，但題目要求不轉字串
- 只反轉一半數字：當反轉部分 >= 剩餘部分時停止，比較兩者是否相等
Approaches
1. Fully Reverse the Number — O(log n) / O(1)
- Idea: 反轉整個數字，比較是否與原數相等
- Time:
O(log n)- 數字位數 - Space:
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. Reverse Half the Number — O(log n) / O(1)
- Idea: 只反轉後半段數字，與前半段比較。當反轉數 >= 剩餘數時停止
- Time:
O(log n) - Space:
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: 反轉一半數字——避免溢位且效率更高
- Key trick: 迴圈終止條件
num > reversed巧妙地表示「處理到一半」，奇數位時用reversed / 10去掉中間位