本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

前言

力扣第九题 回文数 如下所示：

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：

输入： x = 121
输出： true

示例 2：

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

示例 3：

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

示例 4：

输入：x = -101
输出：false

一、思路

这一题题目比较短，也比较容易理解，所以就直接说一下思路。

你想既然要判断整数 X 的正序和倒序是不是一样，那就将整数 x转为字符串 str 。再将字符串 str ，与它的反转字符串比较。

实际的例子：

此处以整数 12345321 为例子
将原字符串与反转后的字符串依次比较，会出现以下两种结果

如都相同：回文数

有不相同的数：不为回文数

经过上面的分析，思路总共就三步：

1. 整数转字符串
2. 获取反转字符串
3. 将两字符串依次比较
复制代码

二、实现

思路有了实现起来也就不是什么难事情了。

实现代码

    public boolean isPalindrome(int x) {
        // 原字符串
        String str = String.valueOf(x);
        // 反转字符串
        String reverseStr = new StringBuilder(str).reverse().toString();
        // 依次比较
        for (int i=0; i<str.length(); i++) {
            // 只要不相等，则返回false
            if (!(str.charAt(i) == reverseStr.charAt(i)))
                return false;
        }
        return true;
    }
复制代码

执行结果

三、如何改进

优化方案一

一顿操作猛如虎，一看击败 20% 。上面的代码是哪里出了问题呢？
其实不难看出，上面反转字符串在某些时候是在做无用功。比如 1234567887654321 这个整数，按照上面的思路光比较字符就需要比较 16次。
为了尽可能的减少比较次数，故从以下两个方面来优化

只需比较字符串的前半部分
排除负数和个位数为0的正数（显然负数和个位数为0的正数均不为回文数）

实现代码

    public boolean isPalindrome(int x) {
        // 负数或个位为0，直接返回
        if (x < 0 || (x%10 == 0 && x != 0)) {
            return false;
        }
        // 原字符串
        String str = String.valueOf(x);
        // 反转字符串
        String reverseStr = new StringBuilder(str).reverse().toString();
        // 依次比较（只比较一半）
        for (int i=0; i<str.length()/2; i++) {
            // 只要不相等，则返回false
            if (!(str.charAt(i) == reverseStr.charAt(i)))
                return false;
        }
        return true;
    }
复制代码

执行结果

显然方案一效果并不明显

优化方案二

不难看出来，方案一中的反转字符串仍会消耗较大的时间。为了追求效率，不能再使用字符串进行比较了。那么如何实现呢？
其实也很简单，拿整数 X 的前半部分与 x 的后半部分反转进行比较。如 123321 的前半部分为 123 后半部分的反转为 321，显然 123321 为回文数。

巧妙的反转

x：原整数
reversX：反转后的整数

具体操作分为以下两步：

每次取 x 的最低位 t ，即 t = x%10
赋值给 reversX ，即 reversX = reversX * 10 + t （ x 中的低位在 reversX 中是高位）

代码实现

考虑到整数的长度（奇偶）

长度为偶数：x == reverseX

常熟为奇数：x == reverseX / 10

    public boolean isPalindrome(int x) {
        // 负数或个位为0，直接返回
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reverseX = 0;
        while (x > reverseX) {
            // 整数最低位
            int t = x % 10;
            // 转为反转后的整数的高位
            reverseX = reverseX * 10 + t;
            // 丢弃最低位
            x /= 10;
        }

        // 如整数长度为奇数，则应为 x == reverseX / 10;
        return x == reverseX || x == reverseX / 10;
    }
复制代码