每日一道 LeetCode (3)：回文数

前文合集

每日一道 LeetCode 文章合集

题目：回文数

题目来源： https://leetcode-cn.com/problems/palindrome-number/

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

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:

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

解题思路

在题目给出的示例中可以直观的看到，负数由于负号的关系，肯定不是回文数的，那么我们第一件事情就是判断输入的数字不是负数。

然后根据数字的特性，还可以知道个位数字是 0 的整数，肯定也不会是回文数，个位是 0 的数字如果是回文数的话，那么首位一定也要是 0 ，这种数字除了 0 以外其余的显然都不会是一个回文数。

这样，我们的第一个极限值判断就有了，所有的负数返回 false ，所有个位是 0 且不为 0 的整数也要返回 false 。

接下来，不知道你们会不会想到上一篇文章中的整数反转，将整个输入的数字反转后，得到的结果如果和输入数字一样，那么这个肯定是回文数，不过这么搞的话，我们还需要判断反转后的数字是否溢出，有点麻烦。

那么比较好的方案是啥，当然是直接反转后面一半的数字，与前面一半的数字做比较，如果一样的话，返回 true ，不一样的返回 false 。

数字反转的操作很简单，输入的数字 x 直接循环的取模就好，然后我们再对输入的数字在循环的过程中除以 10 。

问题是我们如何判断反转的位数已经达到了一半？

这个问题可以这么考虑，如果是偶数回文数的情况，X 和 Y 相等的时候，反转的位数就已经到一半了，如果是奇数回文数的情况，那么 X < Y 的时候，反转的位数也到一半了，然后我们对去除 Y 的最后一位，和 X 进行比较，如果相等，那么这个数字就是奇数位的回文数。

写代码

经过上面的分析，代码已经简单到显而易见了：

public boolean isPalindrome(int x) {
    // 先做极限情况判断
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;

    int revertedNumber = 0;

    // 一直循环到 revertedNumber 大于或者等于 x
    while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }

    return revertedNumber == x || x == revertedNumber / 10;
}

到这里，不知道有没有同学会想问，题目上如果没有加那句「不将整数转为字符串」题干，可以怎么解答。

在 Java 中，如果没有这个限制，那这个代码不要简单太多， Java 中的 StringBuilder 和 StringBuffer 都直接提供了 reverse() 方法：

public boolean isPalindrome_1(int x) {
    // 先做极限情况判断
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;

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

小结一下吧：如果以后遇到「整数反转」的问题，基本思路就是循环取模，然后再乘以 10 加起来，需要注意的就是 int 类型有长度限制，注意超限和极限值判断。今天的回文数可以看做一种稍微特殊的「整数反转」问题。