【LeetCode】Palindrome Number

【题目】Determine whether an integer is a palindrome. Do this without extra space.

一道判断是否是回文的题目，回文指 1， 121 这类左右对称的数字或文本，这里要求是对整型作判断。

常规的思路是先找到数字总共有几位，然后判断高位和低位是否相等，相等是回文数。于是得到第一段代码：

public class Solution {
    public boolean isPalindrome(int x) {
        if(x<0)
            return false;
         
        int quotient = x;
        int digits = 0;
        while (quotient!=0) {
            quotient /= 10;
            digits++;
        }
         
        for (int i=1; i<=digits; i++) {
            int high = digits - i + 1;
            int low = i;
                 
            if (getDigit(x, high) != getDigit(x, low))
                return false;
        }
         
        return true;
    }
     
    private int getDigit(int x, int i){
        if (i==1)
            return x%10;
         
        return (x / (int)Math.pow(10, i-1)) % 10;
    }
}

这段代码还需要单独判断位数只有1的情况，否则会在GetDigit()方法里抛错。

而且显然，这段代码完全不能满足题目要求的 without extra space

怎么优化呢？

1. 我是否可以避免去不停判断当前是第几位，也就是避免对getDigit函数做调用？

2. 除法的开销和异常出现的可能性会影响效率和健壮，是否能够想办法改善？

于是得到第二段代码

int Palindrome(int x) {
    if (0 > x)
        return FALSE;

    int len = 1;
    for (len = 1; (x / len) >= 10; len *= 10);

    while (x != 0) {
        int left = x / len;
        int right = x % 10;

        if (left != right)
            return FALSE;
        x = (x%len) / 10;
        len /= 100;
    }
    return TRUE;
}

第一，在第一个for循环中使用累乘10来得到x的最高位，而不是像第一段代码那样获取数字位数。这样漂亮的避免了除运算可能出现的除数为0的错误。

其次，在while循环中通过不断对 x 与当前len取余并除以10获得原始数的十位和最高位-1（len每轮缩小100倍保持与新的x位数一致）。

如此得到的代码更漂亮且效率高于第一段（第一段代码判断位数的时候无论使用三目还是上述代码均有判断分支和更麻烦的计算）。