LeetCode 9: Palindrome Number

问题描述：

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

这道题求回文数字：和第7题一样，这道题也是可以用字符串解法和代数解法。

字符串解法：转化成字符串（含符号），逆转再比较

class Solution {
    public boolean isPalindrome(int x) {
        String str = Integer.toString(x);
        String reversed_x = new StringBuilder().append(str).reverse().toString();
        return reversed_x.equals(str);
    }
}
           

代数解法：

这个思路我是看答案以后才明白，还是需要一点技巧的。

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

思路分析： 要点有两个，首先要人工排除肯定不是的两种情况：（1） 负数 （2）除了数字0以外结尾是0的。

处理方法：对x求除以10的余数，可获得个位数，如果想获得十位数，则需要把x/10，再重复以上求余步骤，以此类推获得百位数字，千位数字。。。（这里用到了一个隐性的知识点，就是整型的相除会舍弃小数点，例如12345/10=1234）。如果不借助堆栈，求完的余数要立刻用到reversed里面，方法是reversed10+余数（为什么要乘以10呢，是因为每一次在后面续位时，前面的几位要纷纷向左让位，即10。比如147*10=1470，相当于把个位的位置让出来给下一个要进来的数）。再有就是通过while （x > reversed_x）控制这个数字在处理到一半的时候停止，如果位数是奇数，循环停止时reversed会比x长一位；若位数为偶数，则循环停止时reversed和x位数相同。这时候再比较x与reversed，正如刚刚说的，若位数为奇数，成为回文数字的条件是reversed/10 = x （因为reversed长一位所以要除以十再比较）；或者位数为偶数时，成为回文数字的条件是reversed = x。必为两者之一，否则不是回文数字。