[LeetCode]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?

---

直接做 Follow up 直接对整数进行操作而不将整数转化为字符串。可以通过取正和取余的数学方法来获得前后数字进行比对，比如1221这个数字，1221/1000则可以得到首位1，1221 % 10 则可以的到末位 1，对首位与末位的数字进行比较，再把中间的22取出来继续进行比较，代码如下：

解法一：

class Solution {
    public boolean isPalindrome(int x) {
        if( x < 0 ) return false;
        int div = 1;
        while (x /div >= 10) div *= 10;
        while( x > 0) {
            int left = x / div;
            int right = x % 10;
            if(left != right) return false;
            x = (x % div) / 10;
            div /= 100;
        } 
        return true;
    }
}

下面是另一种巧妙的解法，首先判断x是否为负数，这里有一个小技巧，由于整数最高位不能是0所以回文数的最低位也不能是0，数字0除外，如果某个正数末位为0，那么就不是回文数。要验证回文数就要验证数字的前半段和后半段是否对称，如果把后半段反转一下和前半段相等就行了。所以可以取出后半段数字进行反转，具体做法是，通过对10取余取出最低为的数字然后加到取出数字的末尾，就是将revertNum 乘以10再加上这个余数,这样反转就完成了，每取一个最低位的数字x就要除以10。这样当revertNum大于等于x时循环停止。如果回文数位数是偶数那么x与revertNum就相等了，如果是奇数那么中间的数字在revertNum的最低位上，除以10后与x相等，代码如下:

解法二

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

下面是另一种解法，如果是回文数，那么就不可能溢出，只要溢出就一定不是回文数，反转后的数字相等那么就是回文数，代码如下:

解法三

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0 || (x % 10 == 0 && x !=0)) return false;
        return reverse(x)==x;
    }  
    public int reverse(int x) {
        int res = 0;
        while(x !=0 ) {
            if (res > Integer.MAX_VALUE / 10) return -1; //判断溢出
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}

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