回文数字

问题描述

在不使用额外的内存空间的条件下判断一个整数是否是回文。回文指逆序和正序完全相同。

示例：

输入：121

输出：true

分析问题

回文数是指正序和逆序完全相同的数，那么我们可以对原数字进行反转，然后将反转后的数字与原数字进行比较，如果相同，则表明该数字是回文数字。不过这里会引入一个问题，就是对原数字进行反转，有可能导致整数溢出的问题。其实，我们只需要对数字的后半段进行反转，如果数字是回文数字，那么它的前半段和反转后的后半段是相同的。例如，对于数字“1221”来说，我们可以将其后半部分“21”反转为“12”，将其与前半部分“12”进行比较，因为相同，所有数字“1221”是回文数字。

下面我们具体来看一下如何反转后半部分的数字。对于数字“1221”来说，我们对其执行取余操作，即1221 % 10，将得到最后一位数字1；要想得到倒数第二位数字，我们可以先除以10，再对10取余，即 1221/10=122，122%10=2。然后把最后一位数字乘以 10，再加上倒数第二位数字，即1 * 10 + 2 = 12，就得到了我们想要的反转后的数字。如果继续这个过程，我们将得到更多位数的反转数字。

下面我们来看一下如何判断反转数字的位数已经达到原始数字位数的一半？由于整个过程我们不断将原始数字除以 10，然后给反转后的数字再乘上 10，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半的数字了。

更多图解高频算法，请关注公众号【程序员学长】，100多道高频算法题尽在这里，欢迎大家

下面我们来看一下代码的实现。

class Solution:
    def isPalindrome(self, x):
        #负数都不是回文数，所以返回false
        if x<0:
            return False
        #如果数字的最后一位是0，为了使该数字为回文，
        #则其第一位数字也应该是0，所以只有0可以满足
        if x%10==0:
            if x==0:
               return True
            else:
               return False
        revese=0
        while revese<x:
            tmp=x%10
            revese=revese*10+tmp
            x=int(x/10)

        #当数字长度为奇数时，我们可以通过revese / 10去除处于最中间的数字。
        return x == revese or x == int(revese / 10)