力扣-9. 回文数（Palindrome Number）

最后编辑于2025-06-04

9. 回文数（Palindrome Number）

Easy

给定一个整数 x，若 x 是回文整数则返回 true，否则返回 false。

示例 1：

输入： x = 121
输出： true
解释： 从左到右和从右到左都是 121。

示例 2：

输入： x = -121
输出： false
解释： 从左到右为 -121，从右到左为 121-，因此不是回文。

示例 3：

输入： x = 10
输出： false
解释： 反向为 01，因此不是回文。

约束：

  • -2^{31} <= x <= 2^{31} - 1

进阶： 你能在不将整数转换为字符串的情况下解决此题吗？

思路与常见解法

把整数转换为字符串后判断回文是最直接的方法，但进阶要求不允许字符串转换，可以用以下数学方法：

  1. 首尾位比较（取整/取余法）：通过计算除数 div（使 x/div 得到最高位），比较最高位与最低位（x%10），然后去掉首尾继续比较。需要注意更新 div（每次去除两位后 div 除以 100）。

  2. 翻转后半段（反转半段法）：将数字的后半段反转，直到反转后的数 revertNum >= 剩余的 x 为止；若为回文则两者相等（偶数位）或 revertNum/10 == x（奇数位）。此方法无需处理溢出（若溢出则不是回文）。

  3. 直接调用反转并比较（借助 Reverse Integer）：若反转后的值与原值相等则为回文，但需注意反转可能溢出，若溢出则直接返回 false。

下面给出三种实现。

方法一：首尾位比较（取整/取余）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int div = 1;
        while (x / div >= 10) div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10; // 去掉首尾两位
            div /= 100;
        }
        return true;
    }
};
  • 时间复杂度： O(log10(x))（位数相关）
  • 空间复杂度： O(1)

方法二：翻转后半段（反转半段法）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertNum = 0;
        while (x > revertNum) {
            revertNum = revertNum * 10 + x % 10;
            x /= 10;
        }
        return x == revertNum || x == revertNum / 10;
    }
};
  • 时间复杂度： O(log10(x))
  • 空间复杂度： O(1)

方法三：反转并比较（复用 Reverse Integer）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        return reverse(x) == x;
    }
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            if (res > INT_MAX / 10) return -1;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};
  • 说明： 若反转过程中发生溢出，则返回 -1，表示不是回文。

作者想说的话：
不使用字符串时，可以通过取整/取余或反转后半段两种数学方式判断回文，二者时间复杂度均与数字位数成正比，且空间复杂度为常数。