No.9 回文数

题目描述

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例：

输入: 121
输出: true

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

解法一：

思路：利用两个字符串判断是否回文，第一个字符串s1存储原来的整数，第二个利用StringBuilder动态生成反转后的整数。最后再将StringBuilder转化为String与s1比较。
代码：

class Solution {
    public boolean isPalindrome(int x) {
        if (x<0) return false;
        String s1 = x+"";
        StringBuilder s2 = new StringBuilder();
        while(x/10>0) {
            s2.append(x%10);
            x /=10;
        }
        s2.append(x%10);
        return s1.equals(s2.toString());
    }
}

分析：利用字符串处理这个问题，不需要考将虑溢出的问题；但处理的规模为N，利用其它算法可改进为N/2。
改进：不需要拆分整数，转化为字符串后，利用reverse函数实现字符串反转。

String reverseNumber = new StringBuilder(String.valueOf(x)).reverse().toString();  
        return reverseNumber.equals(String.valueOf(x));

解法二：

思路：只处理后半段数字，将后半段数字反转以后与前半段数字对比。如1221，将后半段21反转为12，与前半段一致，所以1221为回文数。
难点：
1.如何将后半段数字反转？
答：拆分整数。

反转整数 = 0;
while(循环条件) {
    末位 =x % 10;
    反转整数 = 反转整数*10 + 末位；
    x /= 10;
}

2.如何做到只处理后半段的数字？
答：原数总是进行除10，反转数进行*10，当原数<反转数时停止循环。

3.奇数和偶数的处理有所差别，如何解决？
答：举个例子，12321为原数x。

第一次循环：
末位 = 12321 % 10 = 1；
反转整数 = 0 * 10 + 1 = 1;
x = 12321/10 = 1232;

第二次循环：
末位 = 1232 % 10 = 2；
反转整数 = 1 * 10 +2 = 12;
x = 1232/10 = 123;

第三次循环：
末位 = 123 % 10 =3；
反转整数 = 12 * 10 +3 = 123;
x = 123/10 = 12;
此时x<反转整数，循环终止！反转整数正好多了中间的3，将反转整数/10即可。

代码：

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