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
注意:
- 此方法不需要将整个数字反转
- 只需要反转一半数字即可判断
- 对于大数处理更有效率