LeetCode每日一练（回文数）-一一网

这是我参与8月更文挑战的第4天，活动详情查看：8月更文挑战

题目如下：

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

判断一个数是否为回文数，首先想到的办法就是将其转为字符串，再通过反转字符串来判断是否相同，比如：

反转后字符串不相同，则不是回文数。

反转后数字相同，则是回文数。由此得代码如下：

public class Solution {

    public static void main(String[] args) {
        System.out.println(isPalindrome(121));
    }

    public static boolean isPalindrome(int x) {
        // 将数字转为字符串
        String str = String.valueOf(x);
        // 将其反转
        String newStr = new StringBuilder(str).reverse().toString();
        return str.equals(newStr);
    }
}
复制代码

提交到LeetCode：

题目的最后还提出了一个进阶要求：

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

不借助字符串该如何实现呢？其实也非常简单，通过计算直接反转数字即可，以1234举例，首先我们需要获得该数字的个位数4，如何获取呢？求余10即可：

接下来获取十位数3，先让1234除以10，这样就得到数字123，再让123求余10即可得到3：

以此类推，就能够得到数字中的每一位：

再让每一位分别乘以对应的进位即可，那既然是要反转，我们就要反着来，将4看成千位，3看成百位，2看成十位，1看成个位：

由此得到反转后的数字：4 * 1000 + 3 * 100 + 2 * 10 + 1 = 4321。

代码如下：

public class Solution {

    public static void main(String[] args) {
        System.out.println(isPalindrome(121));
    }

    public static boolean isPalindrome(int x) {
        int num = x;
        int result = 0;
        // 将数字反转
        while (x > 0) {
            result *= 10;
            result += x % 10;   // 求得每一位
            x /= 10;            
        }
        return num == result;
    }
}
复制代码

但这个程序还有一个小漏洞，就是越界问题，当某个数字反转后大于了int的最大值，那么程序就会出错：

此时result因为超过了int能表示的最大值，已经变成了一个负值，它永远不可能与输入的值相等，所以程序就无法准确判断输入的值是否为回文数了。

为了解决这一问题，我们可以不反转所有的数字，而是反转其中的一半，因为回文数的性质，使得我们只需要知道其中的一半相同，那么它就一定是回文数。

我们需要分两种情况讨论一下，首先是奇数长度的数字，以12321举例：

我们得到反转后一半长度的数字：

将它与反转前一半长度的数字比较，发现均为12，表明12321就是一个回文数。

若是偶数长度的数字，以1221举例：

仍然得到反转后一半长度的数字：

将其与反转前一半长度的数字比较即可。

那么关键在于如何进行数字的切割和获取呢？我们将奇数长度和偶数长度的数字放在一起讨论一下：

首先让其求余10即可得到最后一位数：

接着让原来的数除以10即可舍去最后一位：

再求余10得到最后一位：

再让原来的数除以10舍去最后一位：

到这里就应该停止操作了，因为偶数长度情况的数已经获取到了一半长度的数字，对于偶数情况，直接比较新生成的数字是否与原数字相等即可；而对于奇数长度情况，虽然获取到了一半长度的数字，但原数字中的长度为3，所以我们应该再获取一次：

由此可得，循环的终止条件为当原来的数小于或者等于新生成的数，而对于奇数情况，我们需要去除最后一位数再与原数字比较，所以让新生成的数字除以10再比较。

综上所述，得到代码：

public class Solution {

    public static void main(String[] args) {
        System.out.println(isPalindrome(12321));
    }

    public static boolean isPalindrome(int x) {
        // 负数一定不是回文数
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            // 若是数字的最后一位是0，则如果是回文数，那该数的第一位一定为0，满足情况的数字只有0
            // 所以若是最后一位为0，但该数又不是0，则直接返回false
            return false;
        }
        int newNum = 0;
        // 当原数字小于或等于新生成的数字时停止循环
        while (x > newNum) {
            newNum *= 10;
            newNum += x % 10;
            x /= 10;
        }
        // 比较新生成的数字是否与原数字相等
        return x == newNum || x == newNum / 10;
    }
}
复制代码