leetcode - 0009 回文数

[meishaoming]

https://leetcode-cn.com/problems/palindrome-number

这题在第 5 题做过啊。只不过之前判断一个字符串是不是回文，这里判断的是一个整数。

解法一

整型转字符串，先把之前的解法拿过来用吧

class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        for i in range(len(s) // 2):
            if s[i] != s[-(1+i)]:
                return False
        return True

能过。

写得更 python 一点

看了一下答案中其它人的写法，非常骚。我还是 naive 了。

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

速度都差不多。甚至我之前的下标解法可能更快，因为不用生成一个完整的反序列，只用下标索引就很快能判断结果。

解法二

题目里说不转成字符串来试试

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x == 0:
            return True
        elif x < 0:
            return False
        else:
            r = 0
            n = x
            while n:
                r = r*10 + n % 10
                n //= 10
            return r == x

但是好慢啊。

解法三

看了答案，原来有个技巧。解法二中把整个整数反转，但实际上只反转一半的数就行了。这样减少了一半反转工作，又不用考虑溢出问题（我在解法二中直接忽略了溢出问题）。

如何判断反转了一半？

原始数 x /= 10，反转数 r = r*10 + x%10 。当 x 小于 r 时，就意味着我们已经处理了一半位数的数字。

这个成立的前提是已经把结尾为 0 的情况（如：1230，12300）剔除了。所以：

• 如果长度是奇数，x < r 时，肯定是转过一半+1了。比如 12345，转成了 12 和 543 ，此时要比较 x == r//10
• 如果长度是偶数位，转到一半时，x 已经变成了 0，所以肯定有 x < r

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

但提交的结果并没有很快。