开放原子开发者工作坊

导航页-LeetCode专题-Python实现

相关代码已经上传到github：https://github.com/exploitht/leetcode-python
文中代码为了不动官网提供的初始几行代码内容，有一些不规范的地方，比如函数名大小写问题等等；更合理的代码实现参考我的github repo

1、读题

Determine whether an integer is a palindrome. Do this without extra space.

这一题描述很简单，判断一个数字是否是回文数，不要用额外的空间。其实我觉得逻辑不是那么简答，2个点需要注意，怎样的数字是回文数和怎样算不使用额外空间？

1、先考虑什么数字是回文数？

• 121是回文数
• 1221是回文数
• 1001是回文数
• 0-9都是回文数
• 负数都不是回文数

2、怎样理解不占用额外空间？

写代码肯定需要一定的内存空间，一点都不用就表示随意一个操作都可能违规。所以这里我理解的就是空间复杂度是O(1)，也就是不管你给什么数字，我的算法占用空间恒定，而且不大。

写python的可能很容易想到把数字12345转换成序列类型然后反转判断反转前后是否相同来判断回文数，但是这样明显多出来了2个字符串对象，字符串和数字可不一样，字符串的基本单位是字符，字符才是和数字一个级别的，通俗讲数字12和1234占用空间一样，字符串12和1234差了约一半。也就是说我们可以操作数字本身，但是不能“投机取巧”空间换时间。

2、解题

怎样操作一个数字呢？判断回文数直接的想法是取首尾然后比较是否相等，相等则去掉首尾，继续比较下一个。
怎样取出最后一位呢？观察如下等式：
1234 % 10 = 4
1234 // 10 = 123
这样就分离出来了123和4

怎样取出第一位呢？
1234 // 1000 = 1
1000是1234的数量级
数量级可以通过1234 // 10 > 10; 1234 // 100 > 10; 1234 // 1000 < 10 来找到1000这个数字

这种算法涉及到寻找位数，更麻烦的是遇到1001这种回文数要做额外判断和处理，不然1001去掉首尾变成0了，虽然1001处理结果还算对的，但是10011这种就躲不过去了，去掉首尾得到1，明显逻辑错误了。鉴于这种实现比较low，这里不贴实现了。

略

3、第二种思路

题目的提示中说到反转一个整数，然后比较反转前后的数字，也可以判断回文数，只是需要注意反转可能导致溢出。既然反转是一个思路，又要考虑溢出问题，怎么办呢？观察数字：
123456789和123454321，需要处理的数字既然全反转可能会变大导致溢出，那么反转一半会怎样呢？
给定一个数字12344321如果处理成1234 1234,2个数字相等，那么就是回文数。
给定一个数字123454321如果处理成1234 12345，仅末尾不同，那么也是回文数。
需要注意的是0结尾的数字1210这种不单独处理容易被上面算法处理成回文数。

反转的思路和第二部分解题分析的类似，因为1234%10就能拿到最后一位
4 * 10 + 123 % 10就能拿到43，也就是后2位的反转结果，于是有了如下解法：

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
         # 0-9是回文数
        if 0 <= x <= 9:
            return True
        # 负数和0结尾的不是回文数
        if x < 0 or x % 10 == 0:
            return False
        tmp = 0
        while x > tmp:
            tmp = tmp * 10 + x % 10
            x = x / 10
        if x == tmp or x == tmp / 10:
            return True
        else:
            return False