当前位置：首页 > article >正文

LeetCode【0009】回文数

article 2024/11/14 23:01:29

本文目录

1 中文题目
2 求解思路
- 2.1 基础解法：数字反转法
- 2.2 优化解法：双指针数学法
- 2.3 最优解法：取一半数字法
3 题目总结

1 中文题目

给你一个整数 x ，如果 x 是一个回文整数，返回 True ；否则，返回 False 。
说明：

回文数：是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是
不能将整数转换成字符串，再去比较

示例 1：

输入：x = 121
输出：True

示例 2：

输入：x = -121
输出：False
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：False
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

$-2^{31} \leq x \leq2^{31} - 1$

2 求解思路

2.1 基础解法：数字反转法

思路
将整个数字反转后与原数字比较，如果相等则为回文数。需要注意负数不可能是回文数，并且要处理反转时可能的整数溢出问题。

Python代码

class Solution:
    def isPalindrome(self, x: int) -> bool:
        """
        判断一个整数是否是回文数
        
        参数:
            x: 输入的整数
            
        返回:
            布尔值，表示是否是回文数
        """
        # 处理负数和以0结尾的非0数
        # 负数不可能是回文数
        # 除0以外，以0结尾的数不可能是回文数
        if x < 0 or (x != 0 and x % 10 == 0):
            return False
            
        # 处理0-9的个位数
        if x < 10:
            return True
            
        # 反转整个数字
        original = x
        reversed_num = 0
        
        # 逐位反转数字
        while x > 0:
            # 获取最后一位数字
            digit = x % 10
            
            # 处理溢出情况
            # Python不需要处理溢出，但如果在其他语言中需要处理
            if reversed_num > 214748364:  # 2^31-1 = 2147483647
                return False
                
            # 构建反转后的数字
            reversed_num = reversed_num * 10 + digit
            
            # 去掉原数字的最后一位
            x //= 10
            
        # 比较原数字和反转后的数字是否相等
        return original == reversed_num

时空复杂度分析

时间复杂度分析 O(log n)
- 需要遍历数字的每一位
- n的位数大约是log10(n)
空间复杂度分析 O(1)
- 只使用了几个变量
- 不需要额外的数据结构

2.2 优化解法：双指针数学法

思路
通过数学运算获取数字的最高位和最低位（不转换为字符串），从两端向中间比较。使用除法获取最高位，取模获取最低位，每次比较后通过数学运算去除首尾数字，继续比较剩余部分，直到处理完所有位数。

python代码

class Solution:
    # 直接使用除法和取模
    def isPalindrome(self, x: int) -> bool:
        """
        使用除法和取模的方式实现双指针比较
        """
        # 处理负数和以0结尾的非0数
        if x < 0 or (x != 0 and x % 10 == 0):
            return False
            
        # 计算除数（用于获取最高位）
        div = 1
        while x // div >= 10:
            div *= 10
            
        # 从两端向中间比较
        while x > 0:
            # 获取最高位和最低位
            left = x // div
            right = x % 10
            
            # 比较最高位和最低位
            if left != right:
                return False
                
            # 去掉最高位和最低位
            x = (x % div) // 10
            # 除数要减少两位
            div //= 100
            
        return True

时空复杂度分析

时间复杂度分析 $O (l o g n)$
- 计算位数需要 $O (l o g n)$
- 比较过程需要 $O (l o g n)$
空间复杂度分析 $O (1)$
- 只使用了固定数量的变量
- 不需要额外的数据结构

2.3 最优解法：取一半数字法

思路
将数字后半部分反转，只需要一个简单的判断条件就能同时处理奇数位和偶数位的情况。当原数等于反转数或原数等于反转数去掉最后一位时，就是回文数。

算法步骤举例：

对于偶数位数字1221：

x=1221, reversed_num=0
x=122, reversed_num=1
x=12, reversed_num=12
12 == 12 为true

对于奇数位数字12321：

x=12321, reversed_num=0
x=1232, reversed_num=1
x=123, reversed_num=12
x=12, reversed_num=123
12 == 123//10 为true

python代码

class Solution:
    def isPalindrome(self, x: int) -> bool:
        """
        取一半数字法的简洁实现
        
        参数:
            x: 输入的整数
            
        返回:
            布尔值，表示是否是回文数
        """
        # 处理特殊情况：负数和以0结尾的非0数
        if x < 0 or (x != 0 and x % 10 == 0):
            return False
            
        # reversed_num存储反转后的后半部分数字
        reversed_num = 0
        
        # 当原始数字大于反转数字时继续处理
        # 这确保我们只处理后半部分数字
        while x > reversed_num:
            # 取出x的最后一位，加入到反转数字中
            reversed_num = reversed_num * 10 + x % 10
            # 去掉x的最后一位
            x //= 10
            
        # 统一处理奇数位和偶数位的情况：
        # 偶数位：x == reversed_num （例如：1221）
        # 奇数位：x == reversed_num//10 （例如：12321）
        return x == reversed_num or x == reversed_num // 10