第9题：回文数

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

输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:
你能不将整数转为字符串来解决这个问题吗？

V1版本

这题一看就知道最少两种解法，先用第一种解法试试水，转成string然后进行对比
首先要知道的是
1.负数肯定不是回文数
2.个位数肯定是回文数
代码如下

    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        } else if (x < 10) {
            return true;
        }
        String xStr = String.valueOf(x);
        int lentgh = xStr.length() - 1;
        // 比较两头的数是否相同
        for (int i = 0; i <= lentgh/2; i++) {
            if (xStr.charAt(i) != xStr.charAt(lentgh - i)) {
                return false;
            }
        }
        return true;
    }

image.png

代码虽然简单易懂，不过执行效率也是不出所料的

V2版本

V1版本将数字转成字符本身就需要额外的空间，V2版本按要求进阶
既然是回文数，那么右边翻转过来肯定和左边不是一样的，同时需要考虑数字的长度是奇数位的情况
代码如下

public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        } else if (x < 10) {
            return true;
        } else if (x % 10 == 0) {
                        // 开始反转时，发现遇到10，20的时候处理不对，后面发现这种数都不是回文串，直接先排除
            return false;
        }
        // 用于记录翻转的值
        int num = 0;
        while (x > num) {
            num = num * 10 + x % 10;
            x /= 10;
        }
        /**
         * 例：1221
         * 翻转后x=12,num=12,成功
         * 例：121
         * 翻转后x=1,num=12,因为数的长度是奇数位，num需要去掉中间的2才能匹配
         */
        return num == x || num/10 == x;
    }

image.png

执行结果和上面一样，效率并没有提到提升，去找找官方的实现思想看看

V3版本

看了一下官方的版本，主要是提前判断那里不一样
官文的是

// 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

发现我的判断改成官方的这种方式，时间也能得到提升，一个判断竟然差距这么大

image.png

看到精选里还有一种数学解法

image.png

不过这种解法效率感觉更差一点，就没去实现，多了解一中思路而已