9. 回文数

---

引言

编写通过所有测试案例的代码并不简单，通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例，但如果不了解代码背后的思考过程，那么这些代码可能并不容易被理解和接受。我编写刷题笔记的初衷，是希望能够与读者们分享一个完整的代码是如何在逐步的理性思考下形成的。我非常欢迎读者的批评和指正，因为我知道我的观点可能并不完全正确，您的反馈将帮助我不断进步。如果我的笔记能给您带来哪怕是一点点的启示，我也会感到非常荣幸。同时，我也希望我的分享能够激发您的灵感和思考，让我们一起在编程的道路上不断前行~

回文数

题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

• 回文数：正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如，121 是回文，而 123 不是。

---

示例 1:

• 输入: x = 121
• 输出: true

示例 2:

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

示例 3:

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

---

提示

• -2³¹ <= x <= 2³¹ - 1

---

题意分析

根据示例，我们可以总结出以下规律：

1. 依据示例2，对于负整数，由于存在"-"号，不可能构成回文数；
2. 依据示例3，对于末尾数字为0的整数(0除外)，不可能构成回文数，因为0不可能出现在正整数开头。

因此，对于符合规律1/2的输入，我们可以先通过if语句直接返回False；

即：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False

解决方案1：【反转字符串】

图1 题目暗示

题意告诉我们，进阶做法是不能基于字符串解决【回文数】这个问题 ===> 基于字符串的做法应该比较简单且容易上手。

实际上，基于字符串的解法确实非常简单，

完整代码如下：

class Solution:
    def isPalindrome(self, x: int) -> bool:
        x_str = str(x) # 将整数x转换为字符串x_str
        return x_str == x_str[::-1]

从代码中可以看出，我们只需要三步即可解决【回文数】问题：

1. 利用str()将整数x强制类型转换为字符串x_str；
2. 利用[::-1]将字符串反转；
3. 比较反转前和反转后的字符串是否一致，一致则是回文数，返回True，否则返回False；

运行结果：

图2 运行结果

解决方案2：【反转整数】

问题1：如果题目不提示【字符串】解法，一般我们会想到什么方法呢？

我们一般不会离开"整数"这个范畴去解决问题 ===> 正常步骤应该是：

1. 将整数x进行反转，变成另一个整数x_reverse；
2. 比较反转前的x和反转后的x_reverse，判断这两个整数是否相等，相等则是回文数，返回True，否则返回False；

完整代码如下：

class Solution:  
    """  
    判断一个整数是否是回文数。  
      
    Args:  
        x (int): 待判断的整数。  
      
    Returns:  
        bool: 如果x是回文数，则返回True；否则返回False。  
    """  
    def isPalindrome(self, x: int) -> bool:  
    	# 边界条件
        if x < 0 or (x % 10 == 0 and x != 0):  
            return False  
  
        # 初始化反转后的数为0  
        x_reverse = 0  
        # 保存原始的x值，以便后面与反转后的数进行比较  
        x_tmp = x  
        # 当x_tmp大于等于1时执行循环，将x_tmp的个位数逐个取出并放到反转后的数中  
        while x_tmp >= 1:  
            # 当前取出的个位数为 x_tmp % 10 
            x_reverse = x_reverse * 10 + x_tmp % 10  # 当前反转数乘以10 + 当前取出的个位数
            # 将x_tmp除以10，去掉当前个位数  
            x_tmp = x_tmp // 10  
        
        
        return x_reverse == x

运行结果：

图3 运行结果

复杂度分析

• 时间复杂度：O(logn)，其中 n 为输入的整数。
• 空间复杂度：O(1)
  • 只需要常数空间存放若干变量 ===> O(1)

细节1：尽管将整数完全反转可以通过所有测试用例，但如果题目不仅要求输入x满足 -2³¹ <= x <= 2³¹ - 1，而且要求反转后的x_reverse也满足 -2³¹ <= x_reverse <= 2³¹ - 1，那么将整数完全反转可能会导致x_reverse溢出。

由于2³¹ - 1 = 2147483647，如果整数x=2147483647，那么x_reverse=7463847412 > 2³¹ - 1 ⇒ x_reverse溢出。

图3 示例结果

问题2：为什么把x=2147483647作为测试用例时，将整数完全反转的算法仍然能通过呢？

在Python3中，整数类型只有int，没有限制大小！！！ ⇒ 理论上，Python 3中的整数没有上限（只要不超出内存空间）⇒ 将整数完全反转的算法面对有溢出风险的输入仍能顺利运行。

题外话

实际上，方案2仍然有进一步优化的空间，因为我们一直没有使用回文数的一个重要性质：对称性 ⇒ 我们实际上只需要反转一半的数字，就可以判断输入x是否为回文了。

参考链接

结束语

• 亲爱的读者，感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见，因此在这里鼓励您对我们的博客进行评论。
• 您的建议和看法对我们来说非常重要，这有助于我们更好地了解您的需求，并提供更高质量的内容和服务。
• 无论您是喜欢我们的博客还是对其有任何疑问或建议，我们都非常期待您的留言。让我们一起互动，共同进步！谢谢您的支持和参与！
• 我会坚持不懈地创作，并持续优化博文质量，为您提供更好的阅读体验。
• 谢谢您的阅读！