1. 首页
  2. LeetCode

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

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

题目:回文数

题目来源: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 。

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

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

这个问题可以这么考虑,如果是偶数回文数的情况,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 类型有长度限制,注意超限和极限值判断。今天的回文数可以看做一种稍微特殊的「整数反转」问题。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code