回文数——从字符串到数学，再到工程取舍

一、什么是回文数？

回文数：正着读和反着读都一样。

例如：

121   → 是
1221  → 是
123   → 不是
-121  → 不是

---

二、解法一：字符串法

最直观的思路：

整数
 ↓
转成字符串
 ↓
比较左右字符
bool isPalindrome(int x)
{
    // 负数一定不是回文数
    if (x < 0)
        return false;

    char s[32];

    // 整数转字符串
    sprintf(s, "%d", x);

    int len = strlen(s);

    // 从两端向中间比较
    for (int i = 0; i < len / 2; i++)
    {
        if (s[i] != s[len - 1 - i])
            return false;
    }

    return true;
}

这个版本最大的优点就是：

简单、直观、容易写对。

面试现场如果没有要求必须使用数学方法，这种写法非常容易解释。

缺点也很明显：

需要字符串
需要额外空间
依赖 sprintf

在 MCU 中，如果项目对代码体积比较敏感，printf 家族通常不是优先选择。

---

三、解法二：数学提取每一位

不转字符串，直接利用：

x % 10
x /= 10

把数字一位一位拆出来。

例如：

1221

1221 % 10 = 1
122  % 10 = 2
12   % 10 = 2
1    % 10 = 1

得到：

1 2 2 1

然后再使用双指针比较。

bool isPalindrome(int x)
{
    if (x < 0)
        return false;

    // 32 位 int 最大为 10 位十进制数字，
    // 这里多留几个位置作为余量
    int digits[12];
    int len = 0;

    // 特殊情况：0 本身就是回文数
    if (x == 0)
        return true;

    // 从低位开始提取数字
    while (x != 0)
    {
        digits[len++] = x % 10;
        x /= 10;
    }

    // 左右同时向中间比较
    int i = 0;
    int j = len - 1;

    while (i < j)
    {
        if (digits[i] != digits[j])
            return false;

        i++;
        j--;
    }

    return true;
}

核心就是：

digits[len++] = x % 10;
x /= 10;

一个负责取最后一位，一个负责去掉最后一位。

---

四、解法三：只反转一半数字

前面的代码虽然不依赖字符串，但仍然需要数组。

其实连数组都可以不要。

核心思想

回文数只需要比较两边。

所以：

没必要把整个数字反转，只反转后半部分。

例如：

1221

处理过程：

原数字：12
反转部分：12

两者相等，所以是回文数。

再看：

12321

处理到中间时：

原数字：12
反转部分：123

中间的 3 不影响结果，因此：

reversed / 10

去掉中间数字：

123 / 10 = 12

于是：

12 == 12

成立。

bool isPalindrome(int x)
{
    // 负数不是回文数
    // 以 0 结尾的正数也不可能是回文数
    if (x < 0 || (x % 10 == 0 && x != 0))
        return false;

    int reversed = 0;

    // 只反转后半部分
    while (x > reversed)
    {
        // 取 x 最后一位，加到 reversed 后面
        reversed = reversed * 10 + x % 10;

        // 去掉 x 最后一位
        x /= 10;
    }

    // 偶数位：x == reversed
    //
    // 奇数位：
    // reversed 多包含一个中间数字，
    // 所以去掉最后一位再比较
    return x == reversed || x == reversed / 10;
}

这个版本的核心：

reversed = reversed * 10 + x % 10;
x /= 10;

不断把 x 的低位取出来，拼到 reversed 中。

直到：

x <= reversed

说明已经处理到中间位置。

---

五、三种方法对比

方法	思路	额外空间	特点
字符串法	整数 → 字符串 → 双指针	O(n)	最直观
数组法	%10 提取每一位	O(n)	不依赖字符串
反转一半	%10 + /10	O(1)	空间最优

如果只是为了快速写出：

字符串法最直观

如果限制不能使用字符串：

数组法

如果追求：

O(1) 额外空间

就使用：

反转一半数字

---

六、几个关键点

1. 为什么负数一定不是回文数？

例如：

-121

反过来是：

121-

显然不同。

因此：

if (x < 0)
    return false;

---

2. 为什么 10、100、120 都不是回文数？

因为正数如果最后一位是 0：

10  → 01
120 → 021

反转以后位数发生变化，不可能相同。

所以可以直接：

if (x % 10 == 0 && x != 0)
    return false;

注意：

0

本身是回文数，因此必须保留：

&& x != 0

---

3. 为什么 reversed 只反转一半？

因为判断回文只需要比较：

左半部分 == 右半部分的逆序

没有必要把整个数字反转。

因此：

空间复杂度从 O(n)
↓
降到 O(1)

---

七、复杂度

设数字有 n 位：

字符串法：

时间：O(n)
空间：O(n)

数组法：

时间：O(n)
空间：O(n)

反转一半：

时间：O(n)
空间：O(1)

对于 MCU 这种资源有限的环境，O(1) 空间的思路尤其值得掌握。

---

八、最值得记住的不是代码

这道题真正值得掌握的是三个思维：

整数
 ↓
字符串

是一种思路。

整数
 ↓
%10 / 10

是第二种思路。

进一步：

只处理一半
 ↓
降低额外空间

是第三种思路。

所以算法题不只是：

“把答案写出来。”

更重要的是：

同一个问题，可以从不同角度解决，再根据实际场景选择合适的方法。