回文数 Leecode 9. Palindrome Number-蒲公英云

回文数 Leecode 9. Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:
Coud you solve it without converting the integer to a string?

我们先写几个数字：

-12321 //不是回文数
6 //是回文数
10 //不是回文数
123454321 //是回文数
12344321 //是回文数

设传入的数为x。这里我们需要判断一个数是否为回文数，首先小于10的数肯定是回文数，负数肯定不是回文数，十的倍数肯定不是回文数，这里我们可以提前确定。

if(x<0) return false;
if(x<10) return true;
if(x%10==0) return false;

以上条件是可以一眼看出来的，那大于10的回文数怎么判断呢，可以观察一下回文数的特性。

123454321

最高位等于最低位，次高位等于次低位，依次下去。我们想取得高位很麻烦，取到低位倒是很简单，可以用x%10获取到最低位。再用x/=10，我们可以通过循环从最低位到最高位依次获取到1,2,3,4,5,4,3,2,1。我们将这些获得到的数字*10+下一位到最后不就是x？即设获取到的数是num，num = num*10 + x%10；x = x/10；这种办法是行的通的，见下面代码

class Solution{ 
    public boolean isPalindrome(int x) { 
        if (x < 0 || (x != 0 && x%10 == 0)) return false;//小于0,10的倍数都不是回文数
        if (x < 10) return true;//小于10大于等于0的是回文数
        int num = 0;
        int temp = x;
        while (x != 0){ 
            num = num*10 + x%10;//从最低位开始算x的倒置值
            x = x/10;//除以10等下次循环获取次低位
        } 
        return num==temp;//如果倒置值等于x的值则是回文数返回true，否则false
    }
}

这个方法将整个回文数都遍历一遍，很明显回文数是具有对称性的，有没有什么办法可以只遍历一半的回文数解决问题。

如果回文数位数是偶数位的话，例如123321，我们从最低位算倒置数时，遍历到一半，123 等于此时x（123），此时可以判定123321是回文数。

如果回文数位数是奇数位的话，例如1234321，我们从最低位算倒置数时，遍历到一半，123 ，剩下的x为1234，此时怎么判定呢？不管中间数（4）是多少只要此时倒置数等于x/10也能判定此数是回文数。

class Solution{ 
    public boolean isPalindrome(int x) { 
        if (x < 0 || (x != 0 && x%10 == 0)) return false;
        if (x < 10) return true;
        int num = 0;
        while (x > num){ //此时num不能大于x
            num = num*10 + x%10;
            x = x/10;
            if(num == x/10)return true;//奇数位回文数会在这里退出
        } 
        return x == num;//偶数位回文数会在这里退出
    }
}

另一种写法：因为num不能大于等于x，num >= x时会跳出循环，此是如果x == num/10也是回文数（此时回文数是奇数位）。num == x时也是回文数（此时回文数是偶数位）。

class Solution{ 
    public boolean isPalindrome(int x) { 
        if (x < 0 || (x != 0 && x%10 == 0)) return false;
        if (x < 10) return true;
        int num = 0;
        while (x > num){ 
            num = num*10 + x%10;
            x = x/10;
        } 
        return x == num || x == num/10;
    }
}