用python手刃Leetcode(9)：回文数【简单题】

待我称王封你为后i 2022-05-22 06:47 113阅读 0赞

> ##### 前言 #####
> 
> 博客里新开一个“用python手刃Leetcode”的专题，顾名思义，主要目的是记录自己在Leetcode上刷题的过程，代码全程用python3编写，所用网址是：[leetcode中国][leetcode]。这个网址的好处是：1）纯中文，解决了英语不好读题困难的问题；2）网页打开速度快。  
> \`  
> 同时可以看到：目前官网给出的解题代码是用java编写的，并没有给出官方的python解答，本专栏除了尽量使用多种解法给出每道题的python3解答代码之外，还会记录下自己在做题过程中的一些收获和思考。便于以后复习查阅。

##### 题目 #####

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

>  *  示例 1: 输入: 121 输出: true
>  *  示例 2: 输入: -121 输出: false  
>     解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
>  *  示例 3: 输入: 10 输出: false  
>     解释: 从右向左读, 为 01 。因此它不是一个回文数。

##### 方法一: #####

映入脑海的第一个想法当然是将数字转换为字符串，并检查字符串是否为回文。

class Solution:
        def isPalindrome(self, x):
    	    a = str(x)
            n = len(a)#元素个数
            i = 0
            while i<(n//2):
                if a[i] != a[n-1-i]:
                    return False
            return True

这里用了一次循环，在没有其他思路的情况下不失为一种解决方法。但是，这种方法时间复杂度太长，在这里没法通过。

##### 方法二: #####

第二种方法当然就要使用python的切片大法了。这里还详细分了两种思路：第一种思路是，我管你数字是多少，直接利用[  
用python手刃Leetcode(7)：反转整数【简单题】][_python_Leetcode_7]中提到的字符串反转切片大法。转了之后一比较即可。

class Solution:
        def isPalindrome(self, x):
            x = str(x)
            return x == x[::-1]

Amazing！两行代码解决。

还有一种思路就是多考虑了一下输入的数字类型，负数肯定不会是回文数的，直接返回`False` 即可，所以从源头控制一下输入数据，防止做无用的转换字符串、反转操作。

class Solution:
        def isPalindrome(self, x):
            if x < 0:
                return False        
            return int(str(x)[::-1]) == x

虽然代码多几行，但是速度却降下去了。

##### 方法三：只反转一半数字 #####

这个代码的思路是：因为对于回文数字，其后半部分反转后应该与原始数字的前半部分相同。所以只需要截取数字的后半部分并反转，然后再与前半部分比较即可。虽然思路很有意思，但是在这里，相比于上边两种方法，代码长度和时间复杂度都会变长，唯一优点是会节省一部分空间，姑且在这里贴出来。

x1 = str(x)  #将x转换成字符串
            n = len(x1)  #字符串长度
            if n == 1:   #如果输入是个位数，直接返回True
                return True  
            else:
                x2 = x1[n-n//2:] #截取后半段
                if x1[:n//2] == x2[::-1]: #前半段和反转后的后半段比较     
                    return True
                else:
                    return False

最后，调皮的官网给了一个小进阶问题，留待以后解决：

> 进阶: 你能不将整数转为字符串来解决这个问题吗？

[leetcode]: https://leetcode-cn.com/
[_python_Leetcode_7]: https://blog.csdn.net/u013044310/article/details/80720180