09：回文数
2025-02-17
题目描述
题目：
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例
示例 1：
输入：x = 121
输出：true
解释：121 从左向右读是 121，从右向左读是 121。示例 2：
输入：x = -121
输出：false
解释：从左向右读是 -121，从右向左读是 121-。提示
- -2³¹ <= x <= 2³¹ - 1
解题思路
方法一：字符串转换法
将整数转换为字符串，然后判断该字符串是否与其反转后的字符串相同。
class Solution:
def isPalindrome(self, x: int) -> bool:
"""使用字符串来判断整数回文数"""
if x < 0:
return False
reversed_str_num = str(x)[::-1]
return x == int(reversed_str_num)复杂度分析
- 时间复杂度：O(log₁₀n)，需要将整数转换为字符串
- 空间复杂度：O(log₁₀n)，需要存储字符串
示例运行
# 实例用法
sol = Solution()
print(sol.isPalindrome(121)) # 输出 True
print(sol.isPalindrome(-121)) # 输出 False
print(sol.isPalindrome(10)) # 输出 False方法二：数字反转法
通过反转整数的后半部分来判断是否为回文数。这种方法不需要额外的字符串转换，可以减少空间使用。
算法步骤
- 特殊情况处理：负数和以0结尾的数（除了0本身）
- 反转后半部分数字
- 与前半部分比较
class Solution:
def isPalindrome(self, x: int) -> bool:
# 负数不是回文数，以及如果最后一位是 0，那么只有 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
# 当原始数字等于反转后的数字，或者原始数字是反转数字的一半（对于奇数位数字）
return x == reversed_half or x == reversed_half // 10复杂度分析
- 时间复杂度：O(log₁₀n)，需要处理大约一半数字的位数
- 空间复杂度：O(1)，只需要常数级别的额外空间
示例运行
# 示例用法
sol = Solution()
print(sol.isPalindrome(121)) # 输出 True
print(sol.isPalindrome(-121)) # 输出 False
print(sol.isPalindrome(10)) # 输出 False代码说明
方法二详细说明
特殊情况处理
- 负数一定不是回文数
- 以0结尾的数（除了0本身）不可能是回文数
反转过程
reversed_half = reversed_half * 10 + x % 10 # 构建反转数 x //= 10 # 去除末位数字判断条件
- 偶数位数：x == reversed_half
- 奇数位数：x == reversed_half // 10
注意：
- 此方法不需要将整个数字反转
- 只需要反转一半数字即可判断
- 对于大数处理更有效率