数据结构与算法►力扣

9.回文数

9.回文数

题目描述

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

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

  • 例如，121 是回文，而 123 不是。

示例 1：

1
2
输入：x = 121
输出：true

示例 2：

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

示例 3：

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

提示：

  • -231 <= x <= 231 - 1

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

题解

通过题目描述可以得到如下基本信息：

  1. 复数肯定不是回文数
  2. 能被10整除的数肯定不是回文数（0除外）。
  3. 其他的数就考虑反转，对比老数和反转后的数是否相等即可。

反转数字

怎么反转是个关键，比如12321这个数，如何反转呢？就需要除法运算符/和余数运算符%，看下图下的推理图：

回文数推理

根据上图我们可以得出结论：

  1. 首先我们要做除法得到结果a，当a=0的时候终止。
  2. 求余数b，计算反转结果c，c = b + c * 10。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isPalindrome(int x) {
        // 如果是负数，或者是能够被10整除但是不是0的数，都返回false
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int a = x;
        // 反转后的数字
        int c = 0;
        while (a != 0) {
            int b = a % 10;
            c = b + c * 10;
            a /= 10;
        }
        return c == x;
    }
}

提交下

提交结果

反转数字的一半

上面我们是将整个数字反转，其实不必这样，只需要反转一半就好，这时候值需要对比原数字剩余的部分和反转的数字的关系即可，这就要考虑下数字长度是奇数和偶数有区别吗？

偶数情况：1221

偶数情况

其实第三次和第四次是非必须的，因为在第二次的时候已经反转到一半了。

奇数情况：12321

奇数情况

上图中第三次和第四次也是非必须的，第三次中a = 12，c = 123，只需要判断a和c / 10的情况即可。

两种情况：当a <= c的时候就停止循环，最终判断a == c || a == c /10即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isPalindrome(int x) {
    // 如果是负数，或者是能够被10整除但是不是0的数，都返回false
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    int a = x;
    // 反转后的数字
    int c = 0;
    while (a > c) {
        int b = a % 10;
        c = b + c * 10;
        a /= 10;
    }
    return a == c || a == c / 10;
}

运行结果：

运行结果

上面代码可以简化下，我定义了变量a是为了好理解，其实a就是x，变量b也可以去掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isPalindrome(int x) {
    // 如果是负数，或者是能够被10整除但是不是0的数，都返回false
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    // 反转后的数字
    int c = 0;
    while (x > c) {
        c = c * 10 + x % 10;
        x /= 10;
    }
    return x == c || x == c / 10;
}