LeetCode 9. Palindrome Number 题解

LeetCode 9. Palindrome Number 题解题目描述给你一个整数x如果x是一个回文整数返回true否则返回false。回文数是指正序从左向右和倒序从右向左读都是一样的整数。示例 1输入x 121 输出true示例 2输入x -121 输出false 解释从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。示例 3输入x 10 输出false 解释从右向左读, 为 01 。因此它不是一个回文数。解题思路方法一转换为字符串思路将整数转换为字符串检查字符串是否与其反转后的字符串相等复杂度分析时间复杂度O(n)其中 n 是整数的位数。需要遍历字符串一次。空间复杂度O(n)需要存储字符串。方法二反转一半数字思路首先处理特殊情况如果x 0返回false如果x % 10 0 x ! 0返回false反转后半部分数字与前半部分比较当反转后的数字大于等于前半部分数字时停止反转复杂度分析时间复杂度O(log n)其中 n 是整数的位数。需要处理一半的数字。空间复杂度O(1)只需要常数级的额外空间。代码实现方法一转换为字符串class Solution: def isPalindrome(self, x: int) - bool: # 转换为字符串 s str(x) # 检查字符串是否与其反转后的字符串相等 return s s[::-1]方法二反转一半数字class Solution: def isPalindrome(self, x: int) - bool: # 处理特殊情况 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 # 当数字长度为奇数时reversed_half 会比 x 多一位需要除以 10 return x reversed_half or x reversed_half // 10测试用例测试用例 1输入x 121输出true测试用例 2输入x -121输出false测试用例 3输入x 10输出false测试用例 4输入x 0输出true总结本题是一个经典的回文数判断问题主要考察对回文数概念的理解和实现。两种方法各有特点转换为字符串代码简洁易懂但需要额外的空间来存储字符串。反转一半数字空间复杂度更低只需要常数级的额外空间而且避免了处理字符串的开销。在实际应用中反转一半数字的方法通常更受欢迎因为它更高效而且不需要使用额外的空间。这种方法不仅适用于回文数判断问题还可以应用于许多其他需要处理数字反转的问题。掌握这些方法对于解决这类问题非常重要。