学步园

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.

思路：这道题从题意可知，不能使用额外空间。如果将数字逆序可能会超出int的内存。然后我就举了一个例子，例如1234321，如何获得最高位的1？

设f[0]=1,f[1]=10,f[2]=10^2,..f[n]=10^n，则最高位的1=1234321/f[6]，次高位的2=(1234321-1*f[6])/f[5]；最低位的1=1234321%f[1]/f[0],

次低位的2=(1234321-1*f[0])%f[2]/f[1]，总结以上的推导，获得的高位第i位公式为leftNum = num/f[i]，获得低位的第i位公式为

rightNum=num%f[i]/f[i-1]。故代码如下：

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        long long f[11];
        f[0] = 1;
        int i;
        for(i=1; i<=11; ++i)
        {
            f[i] = f[i-1] * 10;
        }    
        int n = 11;
        while(n > 0 && x/f[n] == 0)
        {
            n--;
        }    
        n++;    
        int left = x, right = x;
        int leftNum,rightNum;
        for(i=1; i<=n/2; ++i)
        {
            leftNum = left / f[n-i];
            left -= leftNum * f[n-i];
            rightNum = right % f[i] / f[i-1];
            right -= rightNum*f[i-1];
            if (leftNum != rightNum)
            {
                return false;
            }    
        }    
        return true;
    }
};