Python · 2 分钟阅读
09：回文数
目录
题目
给你一个整数 x，如果 x 是回文整数，返回 True；否则返回 False。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例
输入：x = 121
输出：True 解释：正读 121，反读 121
输入：x = -121
输出：False 解释：正读 -121，反读 121-
输入：x = 10
输出：False 解释：正读 10，反读 01
约束
-2³¹ <= x <= 2³¹ - 1
思路概览
| 方法 | 思路 | 时间 | 空间 |
|---|---|---|---|
| 方法一 | 字符串 + 反转比较 | O(log n) | O(log n) |
| 方法二 | 反转一半数字 | O(log n) | O(1) |
| 方法三（拓展） | 直接将整数转为字符串再反转 | O(log n) | O(log n) |
观察：负数一定不是回文数；以
0结尾的非零数（10, 100, ...）也不可能是。
方法一：字符串法（最直观）
class Solution:
def isPalindrome(self, x: int) -> bool:
s = str(x)
return s == s[::-1]
- 思路：转字符串，反转后比较。
- 优点：实现最简单。
- 缺点：需要额外 O(log n) 的字符串空间。
方法二：反转一半数字（推荐 O(1) 空间）
class Solution:
def isPalindrome(self, x: int) -> bool:
# 1) 负数不行；2) 以 0 结尾的非零数不行
if x < 0 or (x % 10 == 0 and x != 0):
return False
reverted = 0
# 当原数还大于反转部分时，继续反转
while x > reverted:
reverted = reverted * 10 + x % 10
x //= 10
# 偶数位：x == reverted
# 奇数位：reverted 多了一位中间数字，整除 10 后比较
return x == reverted or x == reverted // 10
关键点解释
x % 10取最低位，x //= 10去掉最低位；- 循环终止条件
x <= reverted意味着“已经反转了超过一半”； - 奇数位数（如
12321）时，reverted = 123，x = 12，中间那个数字
落在reverted的最低位，所以比较x == reverted // 10。
复杂度
- 时间：
O(log₁₀ n)—— 处理约一半位数。 - 空间：
O(1)—— 几个变量。
测试用例
def test():
s = Solution()
assert s.isPalindrome(121) is True
assert s.isPalindrome(-121) is False
assert s.isPalindrome(10) is False
assert s.isPalindrome(0) is True
assert s.isPalindrome(12321) is True
assert s.isPalindrome(123321) is True
assert s.isPalindrome(1001) is True
assert s.isPalindrome(1000021) is False
print("all passed")
test()
常见追问
- 能不能完全不用字符串？ 用方法二即可，O(1) 空间。
- 想用
reversed(str(x))写法？ 可以，但每轮都新建迭代器，性能不如切片。return str(x) == "".join(reversed(str(x))) - 能处理负数
-121算回文吗？ 题目要求“不算”；如果业务上需要，需要先把符号
单独处理。