LeetCode 9. 回文数#

标签#

平台：LeetCode
难度：简单
数据结构：无
算法：数学、模拟
解题模式：无

一、题目概述#

给定一个整数 x，判断它是否是回文整数。回文整数指从左往右读和从右往左读都相同的整数。

二、解题思路#

当前实现不把整数转换成字符串，而是只反转数字的后一半。这样可以避免完整反转整数时可能出现的溢出风险。

先排除负数和末尾为 0 的非零数字。然后不断取出 x 的最后一位，拼到 reverse 后面，同时把 x 去掉最后一位。当 x <= reverse 时，说明已经处理到数字中间。

如果数字位数为偶数，最终应满足 x == reverse；如果位数为奇数，中间位不影响回文判断，应满足 x == reverse / 10。

三、执行过程#

如果 x < 0，返回 false。
如果 x != 0 && x % 10 == 0，返回 false。
初始化 reverse = 0。
当 x > reverse 时，取 x % 10 拼到 reverse 后面。
同时令 x = x / 10，去掉已经处理的最后一位。
循环结束后比较 x == reverse 或 x == reverse / 10。

例如 x = 12321：处理后 x = 12，reverse = 123，去掉中间位后 reverse / 10 = 12，因此是回文数。

四、代码实现#

1
public class LeetCode0009PalindromeNumber {
2

3
    public boolean isPalindrome(int x) {
4
        if (x < 0 || (x != 0 && x % 10 == 0)) {
5
            return false;
6
        }
7

8
        int reverse = 0;
9
        while (x > reverse) {
10
            reverse = x % 10 + reverse * 10;
11
            x = x / 10;
12
        }
13

14
        return reverse / 10 == x || x == reverse;
15
    }
16
}

五、关键代码说明#

x < 0：负号只会出现在最左侧，负数不可能是回文数。
x != 0 && x % 10 == 0：非零数字如果末尾是 0，反转后会出现前导零，不可能相等。
reverse：保存已经反转出的后一半数字。
while (x > reverse)：处理到数字中间时停止。
reverse / 10 == x：用于处理奇数位数字，去掉中间位。

六、复杂度分析#

时间复杂度：O(log n)，每次循环都会去掉一位数字。
空间复杂度：O(1)，只使用常量变量。

七、注意事项#

不需要完整反转整个整数，只反转后一半即可。
奇数位数字需要去掉 reverse 的中间位后再比较。
末尾为 0 的非零数字要提前排除。

八、面试知识点：数字反转与溢出控制#

1. 为什么这题可以不用字符串？#

判断回文数最直观的方法是把整数转成字符串，然后使用左右指针比较字符。

当前实现选择数学做法，不转换字符串，而是通过取模和除法反转数字的后一半。这种写法能体现对数字位运算过程的理解，也能避免额外字符串空间。

2. 为什么只反转后一半？#

如果完整反转整个整数，可能会产生整数溢出。例如接近 Integer.MAX_VALUE 的数字，反转后可能超出 int 范围。

当前实现只反转后一半数字。当 reverse >= x 时，说明已经处理到中间位置，可以停止。这样 reverse 的规模最多接近原数字的一半位数，溢出风险更低。

3. 负数为什么不是回文数？#

负数的负号只出现在最左边。

例如 -121 从左往右读是 -121，从右往左读无法得到同样的合法整数表示。因此负数直接返回 false。

4. 为什么末尾为 0 的非零数字不是回文数？#

如果一个非零数字末尾是 0，要成为回文数，它的最高位也必须是 0。

但整数表示不会保留前导零，所以类似 10、100 都不可能是回文数。当前实现用：

1
x != 0 && x % 10 == 0

提前排除这类情况。

5. reverse 是怎么构造的？#

当前代码：

1
reverse = x % 10 + reverse * 10;
2
x = x / 10;

含义是：

x % 10 取出当前最后一位；
reverse * 10 给已经反转的数字整体左移一位；
x / 10 去掉原数字最后一位。

例如 x = 1221：

1
第一次：x = 122, reverse = 1
2
第二次：x = 12, reverse = 12

此时 x == reverse，说明是偶数位回文。

6. 奇数位和偶数位怎么判断？#

偶数位回文，例如 1221，最终会出现：

1
x == reverse

奇数位回文，例如 12321，中间位不影响结果。最终可能是：

1
x == reverse / 10

这里的 reverse / 10 是为了去掉中间那一位。

7. 取模和除法在这类题里的作用#

数字类题目中，常见技巧是：

x % 10：取最后一位；
x / 10：去掉最后一位；
reverse * 10 + digit：把一位数字追加到反转结果末尾。

整数反转、回文数、数字位求和等题都会用到这套思路。

8. 字符串解法和数学解法怎么比较？#

字符串解法：

思路直观；
容易写；
需要额外字符串空间。

数学解法：

空间复杂度更低；
能体现对数字位处理的理解；
要特别注意负数、末尾零和溢出问题。

本题当前实现使用数学解法，空间复杂度是 O(1)。

9. 时间复杂度为什么是 O(log n)？#

每次循环都会通过 x / 10 去掉一位数字。

一个整数的十进制位数大约是 log10(n)，所以循环次数与数字位数成正比，时间复杂度是 O(log n)。

因为只使用了 reverse 等常量变量，空间复杂度是 O(1)。

10. 回到本题，面试时怎么回答？#

可以这样组织回答：

这道题我没有把数字转成字符串，而是用数学方式反转后一半数字。先排除负数和末尾为 0 的非零数字。然后循环取 x 的最后一位拼到 reverse 上，同时把 x 去掉最后一位。当 reverse >= x 时，说明已经处理到数字中间。
如果是偶数位回文，最后应该满足 x == reverse；如果是奇数位回文，中间位可以忽略，所以判断 x == reverse / 10。这种做法不需要额外字符串空间，时间复杂度是 O(log n)，空间复杂度是 O(1)。