← 目录 / 算法文档 · 模块一 数学基础 / 1.2 回文判断

1.2 回文判断

判断一个数正读、反读是否一样——直接复用上一节的 ReverseNumber,再处理几个容易踩坑的细节。

本页目录
① 什么是回文数

回文数是指一个数从左往右读和从右往左读完全一样,比如 121133112321,乃至单独一个数字 7。"回文"这个词本身来自古代的一种文字游戏——回文诗、回文句,顺着读、倒着读都是同一句话;数学里的回文数,就是把这个概念搬到数字上。

判断"是否对称",本质上是判断每一对"镜像位置"上的数字是否相等:第 1 位要等于最后一位,第 2 位要等于倒数第 2 位,以此类推,一直夹到中间为止。

12321 —— 每一对镜像位置都相等,是回文数
1
2
3
2
1
第1位
第2位
中心
第2位
第1位
12341 —— 看起来很像,但第 2 位和倒数第 2 位不相等,不是回文数
1
2
3
4
1
第1位
2≠4
中心
4≠2
第1位
蓝色一对、粉色一对,是两组"必须相等"的镜像位置;中间绿色是对称轴,落单一个,不需要和谁配对。只要有一对镜像位置不相等(像第二个例子里的 2 和 4),整个数字就不是回文数。
② 基础写法:反转后比较

"每一对镜像位置相等"说起来有点抽象,但换一个角度看:如果把整个数字反转一遍,结果和原数完全一样,那不就正好说明每一位都和它的镜像位置相等吗?这正是上一节 ReverseNumber 能直接派上用场的地方——回文判断的最朴素写法,只需要一行:

C++ · 反转后比较(最朴素的写法)
1bool IsPalindrome(int n)
2{
3 return n == ReverseNumber(n);
4}

试一下:IsPalindrome(121) —— ReverseNumber(121) 算出来还是 121,相等,是回文数;IsPalindrome(123) —— ReverseNumber(123) 算出来是 321,不相等,不是回文数。

两个例子:反转之后比一比
n = 121
==
ReverseNumber(121) = 121
✓ 回文数
n = 123
ReverseNumber(123) = 321
✗ 不是回文数
📌
这种写法的好处是非常直观——不需要纠结"镜像位置"这种抽象描述,反转一下、比一比就完事了。代价是它会把整个数字完整反转一遍,等会在第 ④ 节我们会看到,这个"完整反转"在某些情况下会带来麻烦。
③ 两个容易踩坑的细节

细节一:负数算不算回文数?上一节我们刚学过,n != 0 这个条件能让 ReverseNumber 正常处理负数,那如果直接把负数丢进 IsPalindrome 会发生什么?我们用 -121 试一下:

ReverseNumber(-121) 的真实结果 —— 一个容易被忽略的陷阱
n(待拆分)取出的数字rev(结果累积)
-121-10×10+(-1) = -1
-12-2-1×10+(-2) = -12
-1-1-12×10+(-1) = -121
ReverseNumber(-121) = -121 —— 和原数相等!
因为负号本身也跟着每一位一起被"带"进了计算(每一位都是负数),如果原数去掉负号之后正好是回文(121 就是),反转完的结果会恰好跟原数相等。这样一来,n == ReverseNumber(n) 会把 -121 误判成"是回文数"——但按照通常的约定,负数永远不算回文数(负号本身打破了"从左读到右、从右读到左完全一样"这件事,"-121"倒着读会变成"121-",根本不是同一个东西)。
⚠️
修复方法很简单:在反转之前,先专门判断一下符号,负数直接返回"不是回文数",根本不需要进入后面的反转逻辑:
C++ · 修正:负数直接排除
1bool IsPalindrome(int n)
2{
3 if (n < 0) return false; // 负数不算回文数
4 return n == ReverseNumber(n);
5}

细节二:以 0 结尾的数(但不是 0 本身),需要特殊处理吗?比如 120100 这种数,结尾是 0——直觉上你可能会担心这种情况需要单独写代码处理。其实完全不需要,上一节我们专门讲过"反转之后前导 0 会自动消失",这里正好能用上:

120 不需要额外处理 —— 上一节的"前导0消失"原理直接帮你解决了
n = 120
ReverseNumber(120) = 21
✗ 不是回文数
120 反转之后,末尾的 0 会变成反转结果的开头,但整数没有前导 0 这种东西,所以这个 0 就直接消失了,ReverseNumber(120) 算出来是 21,和原数 120 自然不相等——n == ReverseNumber(n) 已经自动把这种情况正确判断成"不是回文数"了,不需要你额外写一行特判代码。
💡
有些代码(包括很多教辅资料)会在反转之前先加一句 if (n % 10 == 0 && n != 0) return false;,这其实只是一个可选的提前退出优化(省得真的去算一遍反转),并不是必须的——就像上面演示的,不加这句也能得到正确答案。理解"为什么不加也对",比死记"要加这一句"更重要。
④ 进阶写法:只反转一半

基础写法有一个潜在的风险:它会把 n 完整反转一遍。如果 n 本身已经很接近 int 能表示的最大值(约 21 亿),反转之后位数顺序整体颠倒,反转结果可能会超出 int 的范围,导致溢出、结果出错。

解决办法是:既然回文数前后镜像对称,那只需要反转一半,再跟剩下的另一半比较,结果是一样的——但反转的数字始终不会比原数大太多,几乎不会溢出。

C++ · 只反转一半
1bool IsPalindrome(int n)
2{
3 if (n < 0) return false;
4 int rev = 0;
5 while (n > rev) // 只要 n 还比 rev 大,说明还没反转过半
6 {
7 rev = rev * 10 + n % 10;
8 n /= 10;
9 }
10 return n == rev || n == rev / 10;
11}

循环条件变成了 n > rev——只要剩下没反转的那部分(n)还比已经反转出来的那部分(rev)大,就继续反转下一位。当 rev "追上" n 时,说明已经反转了差不多一半,停下来比较。用 12321 走一遍看看每一步:

IsPalindrome(12321) —— 只反转一半的执行过程
循环前 n循环前 revn > rev ?反转后 n / rev
12321012321 > 0 ✓ 继续n=1232 rev=1
123211232 > 1 ✓ 继续n=123 rev=12
12312123 > 12 ✓ 继续n=12 rev=123
1212312 > 123 ✗ 停止
最终 n=12,rev=123 —— n == rev/10(123/10=12),是回文数 ✓
注意最后一步:12321 总共 5 位,是奇数位,中间的 3 在反转过程中被"多算"进了 rev 里(rev=123n=12 多一位)。这时候不能直接比较 n == rev,而要去掉 rev 最后一位(也就是中间那个多出来的数字)再比较:rev / 10 = 12,正好等于 n。如果原数是偶数位(比如 1221),两部分会刚好对半分,直接 n == rev 就够了,不需要再除以 10。
🎯
为什么这样能避免溢出?整个过程中,rev 最多增长到和原数位数差不多一半的规模就停下来了,永远不会超过原数本身的数量级——而基础写法里完整反转一个数,最坏情况下反转结果可能比 int 能装的范围还大。只反转一半,从根本上避开了这个风险。
⑤ 两种写法对比
写法反转范围溢出风险适用场景
反转后比较完整反转整个数字数字接近 int 上限时可能溢出数字不大,追求代码简单直观
只反转一半只反转大约一半的位数几乎不会溢出数字范围较大、或者题目对效率/边界要求更严格
💡
如果判断的是字符串,而不是数字呢?本节讨论的都是"数字"形式的回文(int 类型)。如果题目给的是一个字符串(比如判断 "level" 是不是回文),通常会用双指针——一个指针从最左边出发,一个从最右边出发,往中间逐步靠近,边走边比较两个指针指向的字符是否相等。这个技巧会在模块七·双指针里详细介绍,思路和这一节"镜像位置成对比较"的核心思想是完全一致的,只是不需要先转换成数字。