9. Palindrome Number

题目

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

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

解题思路：
这道题首先要理解什么是回文数字，就是从左到右的数字顺序和从右到左的数字顺序是一样的，比如 12321。判断一个数字是否是回文数字有以下规则

1. 负数不是回文数字。
2. 能被 10 整除的也不是负数，0 除外。
3. 若是数字的位数是偶数位 n，那么从右向左反转 n/2 位数字，然后和剩下的 n/2 位从左向右数字比较，若是相等则是回文数字。 如
   12344321 可以拆解成 1234 和 1234 对比。
4. 若是数字的位数是奇数位 n+1 ,那么从右向左反转 n/2 + 1 位数字得到数字 m，再将 m / 10 去掉个位数的到 q ，然后和剩下的 n/2 位从左向右数字比较，若是相等则是回文数字。如 12321，可以拆解成 12 和 12 对比。

解题代码：

class Solution {
public:
    bool isPalindrome(int x) {
       // 去掉负数和能够被 10 整除的数，0 除外
        if(x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        // 反转数字
        int revertedNumber = 0;
        while(x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber/10;
    }
};

参考

1. https://leetcode.com/problems/palindrome-number/description/