9. 回文数
题目描述
给你一个整数 x，如果 x 是一个回文整数，返回 true；否则，返回 false。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。负数不是回文数。
示例：
- 输入：x = 121，输出：true
- 输入：x = -121，输出：false（负数不是回文数）
- 输入：x = 10，输出：false（正序是 10，倒序是 01，不同）
解题思路
第一步：理解问题本质
回文数的核心特征是：从左读和从右读完全相同。
最直观的理解方式是：把数字的每一位排成一排，第一位和最后一位相同，第二位和倒数第二位相同，以此类推，直到中间。
有一个特殊情况需要先处理：负数一定不是回文数。原因是负号 - 只在最左边，倒过来读就不一样了。例如 -121 倒过来是 121-，不相同。
第二步：暴力解法
最直接的思路是把整数的每一位取出来，存入一个列表，然后判断该列表是否是回文。
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
digits = []
n = x
while n > 0:
digits.append(n % 10)
n //= 10
# digits 是从低位到高位的顺序
# 判断是否回文：digits[i] 应等于 digits[len-1-i]
length = len(digits)
for i in range(length // 2):
if digits[i] != digits[length - 1 - i]:
return False
return True
为什么这个解法不够理想： 需要额外的列表存储每一位数字，空间复杂度为 O(log n)（数字的位数）。对于非常大的数字，这个开销是不必要的。此外，逻辑略显冗长。
第三步：优化解法——转字符串 + 双指针
把整数转换为字符串后，回文判断变得非常直观：用两个指针分别从字符串的左端和右端向中间移动，只要发现对应字符不相等，就返回 false。
这是一种常见且简洁的写法，时间和空间都在可接受范围内。
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
s = str(x)
mid = len(s) // 2
for i in range(mid):
if s[i] != s[len(s) - 1 - i]:
return False
return True
双指针的含义：
i从 0 开始，表示左端指针len(s) - 1 - i是对应的右端位置- 只需检查前一半，因为若前一半全部对称，整体就是回文
为什么只遍历一半： 回文的对称性意味着只需检查 mid 次，不需要遍历全部字符。这个优化让比较次数减半。
不足之处： 将整数转为字符串需要额外的字符串空间，空间复杂度为 O(log n)。
第四步：最优解法——反转一半数字（不转字符串）
进阶思路是：不将整数转换为字符串，而是直接在数字层面判断。
核心思想：将数字的后半段反转，然后与前半段比较。如果两者相等，则是回文数。
为什么只反转一半，而不是整体反转？
若整体反转，存在溢出风险（例如一个很大的数反转后超出 int 范围）。只反转一半可以避免这个问题。
如何知道何时反转了一半？
当"已反转的后半段" >= "剩余的前半段"时，说明后半段已经至少和前半段一样长了，反转完成。
边界条件处理：
- 负数直接返回 false
- 个位数为 0 但本身不是 0 的数（如 10、20）一定不是回文数，因为最高位不可能是 0
class Solution:
def isPalindrome(self, x: int) -> bool:
# 负数不是回文数
# 末位是0但不是0本身，不是回文数（如10反转是01，最高位不能为0）
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
# 偶数位：x == reversed_half（如1221，处理后 x=12，reversed_half=12）
# 奇数位：x == reversed_half // 10（如12321，处理后 x=12，reversed_half=123，去掉中间位）
return x == reversed_half or x == reversed_half // 10
为什么最后要判断两种情况：
- 若原数字有偶数位，如 1221：反转后半段得到 12，前半段剩余 12，直接比较
x == reversed_half - 若原数字有奇数位，如 12321：中间那位（3）属于后半段，反转结果是 123，前半段剩余 12，此时用
x == reversed_half // 10去掉中间那位
完整代码实现
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
s = str(x)
mid = len(s) // 2
for i in range(mid):
if s[i] != s[len(s) - 1 - i]:
return False
return True
示例推演
以 x = 12321 为例，使用转字符串双指针解法：
s = "12321"
len(s) = 5，mid = 5 // 2 = 2
i = 0：s[0] = '1'，s[4] = '1'，相等，继续
i = 1：s[1] = '2'，s[3] = '2'，相等，继续
循环结束（i 只到 mid-1 = 1）
返回 True
以 x = 12345 为例：
s = "12345"
len(s) = 5，mid = 2
i = 0：s[0] = '1'，s[4] = '5'，不相等
返回 False
以 x = -121 为例：
x < 0，直接返回 False
以 x = 10 为例：
s = "10"
len(s) = 2，mid = 1
i = 0：s[0] = '1'，s[1] = '0'，不相等
返回 False
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力（提取各位） | O(log n) | O(log n) | 位数为 log₁₀n，额外列表存储各位 |
| 转字符串双指针 | O(log n) | O(log n) | 字符串长度为 log₁₀n |
| 反转一半数字 | O(log n) | O(1) | 只需常数额外空间，无需转换 |
这里 n 指整数本身的值，log₁₀n 近似于数字的位数。
易错点总结
- 负数的处理：负数一定不是回文数，需要在最开始返回 false，不要忘记这一判断。
- 末尾为 0 的情况：如 10、100 这类数字，末位是 0 但最高位不是 0，一定不是回文数。若用反转一半的方法，需要提前排除这类情况（x != 0 且 x % 10 == 0）。
- 单个数字是回文数：0 到 9 的所有单位数都是回文数，代码中的循环
range(mid)在mid = 0时不会执行，直接返回 true，处理是正确的。 - 双指针的右端计算：
s[len(s) - 1 - i]是正确写法，不要写成s[-i]，后者在 i=0 时访问的是最后一个元素，会导致下标计算混乱。
扩展思考
相关题目：
- LeetCode 125. 验证回文串（字符串版本，需要忽略非字母数字字符）
- LeetCode 234. 回文链表（链表版本，无法用下标访问）
算法本质：
"回文"问题的核心是对称性验证。双指针是处理对称性问题最自然的工具，因为它天然地从两端向中间收缩，每步都在验证对称位置的一对元素。
在字符串、数组、链表等不同数据结构上，验证回文的思路都是一致的：找到中点，然后对称比较两侧。区别在于访问方式：数组可以用下标，链表需要先反转或使用快慢指针找到中点。