对我来说回文数是C入门阶段“最划算”的一类题目。它不像排序、链表那样需要先铺垫一大堆数据结构知识却能把取余、整除、循环、函数封装、边界条件这些基本功一次全练到。很多初学者做完“判断一个整数是不是回文数”这道题就觉得自己会了结果一遇到“求5位数里的所有回文数”“反转一半会不会溢出”“字符串回文和数字回文有什么区别”就开始卡壳。这篇文章我就把回文数相关的经典例题串起来讲一遍从最基础的判定到综合应用每一道题都给出能直接跑的思路和代码也把那些书上一般不写的坑点一起说清楚。1. 判定一个整数是否为回文数三种方法各有适用场景“12321倒过来还是12321”这就是回文数最直白的定义。但在C里实现“倒过来”这件事不同做法对应不同的适用场景面试和考试里常考的区别也在这里。1.1 反转法最直观但要警惕溢出问题第一种思路很直接把整数反转然后和原数比较。比如121反转后还是121那就判定为回文123反转后是321不等于123就不是回文。bool isPalindrome(long long x) { if (x 0) return false; // 负数带负号不是回文 long long temp x, reversed 0; while (temp 0) { reversed reversed * 10 temp % 10; temp / 10; } return reversed x; }很多教科书和竞赛题解都用这个写法但这里有一个非常重要的点反转后的数字可能超出int的表示范围。举一个很经典的例子判断1234567899是不是回文数。这个数本身没有超出int范围int最大值是2147483647但反转之后是9987654321显然超过了int上限。如果你用int reversed去接结果就是溢出后的垃圾值程序会给出完全错误的判定。这就是为什么很多严谨的写法里反转变量要用long long。C标准里long long至少有64位能表示的最大值是9223372036854775807对于常规题目里的回文数判定已经够用了。注意即便用了long long也建议在循环里加一个判断——如果reversed已经大于INT_MAX / 10说明反转后必然溢出可以直接返回false。这不是多此一举而是防御性编程的好习惯。1.2 逐位比较法不产生新数字完全规避溢出既然反转可能溢出那能不能不生成反转后的数字而是直接比较首位和末位这个方法在数学上等价但实现上要稍微绕一点。思路是这样的先算出这个数有多少位然后每次取出最高位和最低位比较它们是否相等不相等就直接返回false相等就“掐头去尾”继续比较剩下的中间部分。以12321为例最高位是万位值1最低位是个位值1相等去掉这两位变成232继续比较最高位2和最低位2相等最后剩下3自然相等判定为回文数。bool isPalindromeByDigit(int x) { if (x 0) return false; int divisor 1; while (x / divisor 10) divisor * 10; // 找到最高位对应的数量级 while (x 0) { int high x / divisor; // 最高位 int low x % 10; // 最低位 if (high ! low) return false; x (x % divisor) / 10; // 去掉最高位和最低位 divisor / 100; } return true; }这段代码里最不好理解的是x (x % divisor) / 10这一句。x % divisor是把最高位切掉比如12321 % 10000 2321再除以10是把最低位也切掉得到232。同时divisor / 100是因为数字少了两位数量级也跟着缩小100倍。这种写法的优势是全程只做取余、整除、比较操作所有中间结果的量级都不会超过原数本身所以不需要担心溢出问题。它的缺点是代码稍微啰嗦而且要注意divisor的更新逻辑稍不留神就会把divisor除错导致死循环。实际工程里我很少用它因为可读性不如反转法但它是一种很重要的“无溢出思维”在嵌入式或大数场景下特别有用。1.3 双指针法字符串化之后最优雅第三种思路是把整数转换成字符串然后用双指针从两头往中间走一一比较。这种方式在LeetCode风格的题目里很常见因为代码短、逻辑清楚也好扩展。bool isPalindromeString(int x) { if (x 0) return false; std::string s std::to_string(x); int left 0, right s.size() - 1; while (left right) { if (s[left] ! s[right]) return false; left; right--; } return true; }这段代码就没必要解释太多了学过数组的都能看懂。它唯一的“额外开销”是把整数转成字符串需要一点临时内存但对于日常练习和竞赛来说这个开销完全可以忽略。我把三种方法放到一起它们各自的特点非常明显方法核心思路优点缺点适用场景反转法反转后比较直观、好理解反转值可能溢出数据范围小的题目逐位比较法首位与末位逐一比对无溢出风险代码略复杂大数、嵌入式场景双指针法转字符串后两头逼近代码简洁、逻辑清晰需要额外字符串空间刷题、工程日常如果你问我在实际项目代码里首选哪个我会选反转法配long long。理由很实际它最容易被后来维护的人看懂而且配合类型选对了完全够用。2. 反转一半数字LeetCode第9题的经典优化思路前面讲的都是“完整反转”但如果数字位数很多完整反转一个几十位的数即使不溢出计算量也是一种浪费。LeetCode第9题给出过一个非常经典的优化思路——只反转数字的后半部分。这个思路的核心观察是像1221这样的偶数位回文数前半部分12和后半部分21反转后相等像12321这样的奇数位回文数前半部分12和后半部分21忽略中间数字3反转后也相等。所以我们不需要把整个数字反转只要把后半部分反转到一个新变量里和前半部分比较即可。实现的关键是循环终止条件当reversed x时停止。这里的x在循环过程中会不断被“砍掉”末位数字。bool isPalindromeHalf(int x) { if (x 0 || (x % 10 0 x ! 0)) return false; // 注意末尾是0的数反转后开头必然是0不可能等于原数 // 比如10反转是01即1不等于10 int reversed 0; while (x reversed) { reversed reversed * 10 x % 10; x / 10; } // 偶数位情况x reversed // 奇数位情况x reversed / 10去掉中间位 return x reversed || x reversed / 10; }以1221为例走一遍初始x 1221reversed 0第一次循环reversed 1x 122第二次循环reversed 12x 12循环结束因为x (12) reversed (12)不成立比较x reversed即12 12成立返回true再以12321为例初始x 12321reversed 0第一次reversed 1x 1232第二次reversed 12x 123第三次reversed 123x 12循环结束因为12 123不成立比较x reversed / 10即12 12成立返回true这个优化最大的魅力在哪里它将空间和时间都控制在了半个数的规模内而且不会出现溢出问题。仔细想想reversed的增长速度跟x的缩短速度是同步的当循环结束时reversed的位数最多是原数的一半它不可能超过原数的量级所以完全不需要long long一个int就够。这也是这道题能被称为“经典”的原因之一——用最小的成本解决问题同时强迫你理解循环边界和奇数偶数的差异。这里有个容易忽略的边界条件我单独拎出来强调负数一律不是回文数这个没什么争议。还有一类是末尾为0的正整数比如10、100、1100它们也一定不是回文数。为什么因为回文数反转后与原数相同如果原数末尾是0反转后开头就是0那么反转结果必然比原数少一位前导零在整数里没有意义所以不可能相等。开头那段代码里x % 10 0 x ! 0这个判断就是为了提前排除这类数省掉无意义的循环。3. 找出所有n位回文数一次循环枚举 vs 构造法判定单个数字是不是回文只是热身真正在作业和比赛里高频出现的是“求所有n位数中的回文数”。比如n5求从10000到99999之间的所有回文数然后统计个数、求和、找质数等等。这个问题的第一反应通常是暴力枚举遍历所有n位数逐个调用isPalindrome判断。这种做法对n5、n6完全没问题但如果n到了8甚至10枚举量会指数增长判定函数即使再快也会力不从心。更聪明的做法是直接构造回文数。一个n位的回文数其实只需要确定前一半的数字后一半自动被前一半决定。比如5位数只要确定前3位包含中间位剩下2位就全部确定了比如6位数只要确定前3位后3位就全部确定了。写成代码就是枚举所有可能的“前半部分”然后把它翻转后拼接到后面#include iostream #include vector #include cmath std::vectorlong long generatePalindromes(int n) { std::vectorlong long result; if (n 0) return result; int halfLen (n 1) / 2; // 需要确定的前半部分长度 long long start std::pow(10, halfLen - 1); // 前半部分的最小值 long long end std::pow(10, halfLen); // 前半部分的最大值不含 for (long long left start; left end; left) { std::string leftStr std::to_string(left); std::string rightStr leftStr; if (n % 2 1) { // 奇数位去掉中间位再反转 rightStr.pop_back(); } std::reverse(rightStr.begin(), rightStr.end()); std::string fullStr leftStr rightStr; result.push_back(std::stoll(fullStr)); } return result; }以n5为例halfLen 3枚举的left范围是100到999。取left 123时因为n是奇数把leftStr末尾的3去掉得到12反转后是21拼接得到12321这正好是一个5位回文数。偶数位更简单n6时left 123直接反转123得到321拼接得到123321。构造法的核心好处有两个计算量大大减少。n5时暴力枚举要判断90000个数构造法只需要枚举900个前半部分。枚举和判断合并成了一步。不需要再调用回文判定函数因为构造出来的必然是回文数。统计个数的公式也顺带着出来了n位回文数的总数等于9 * pow(10, (n-1)/2)。比如n5就是9 * 10^2 900个n6也是9 * 10^2 900个。有趣的是5位和6位回文数的数量是一样的这一点很多初学者第一次看到会觉得意外其实想通了halfLen的关系就明白了。4. 回文数与质数的综合应用从逐个判断到筛法加速如果题目升级成“求出所有5位回文数中的质数”这就不再是单一知识点的练习而是把回文判定和质数判定组合在一起的综合题。这种题目在竞赛里很常见因为它同时考察了数学敏感度和代码能力。先看最简单直接的组合先判断回文再判断质数。bool isPrime(int x) { if (x 2) return false; for (int i 2; i * i x; i) { if (x % i 0) return false; } return true; }然后把两种判定组合起来遍历所有5位数先判断回文再判断质数或者反过来都行。一般来说先判断回文更划算因为回文数少得多能迅速过滤掉大多数数浪费的质数判断变少了。但既然题目叫“综合应用”就应该想得更深一层。偶数位回文数有一个数学性质它们都能被11整除。这个性质来自一个经典结论一个数如果是回文数且位数为偶数那么它一定是11的倍数。这个结论怎么来的其实可以这样理解11的倍数有一个众所周知的判定法——奇数位数字之和与偶数位数字之和的差是11的倍数。以偶数位回文数abcddcba为例奇数位数字为a、c、d、b偶数位数字为b、d、c、a两个和显然相等差为0所以它是11的倍数。这个性质配合质数题目能得到一个大杀器级别的结论除11本身外所有偶数位回文质数都不存在。因为大于11的偶数位回文数一定能被11整除所以不可能质数。于是“5位回文质数”这个问题被大大简化了5是奇数位5位回文数中间那一位可以是0到9但首位不能为0。5位回文质数确实存在比如10301。编程求解时我们只需要枚举100到999的前半部分构造出5位回文数然后判断质数即可。如果把数据范围扩大到所有位数我们甚至可以先按位数分类偶数位的直接跳过除了11本身只有奇数位才需要真正跑质数检测。这样一个简单的数学观察能把计算量直接砍掉一半。实战心得这种“先利用数学性质缩小搜索范围再写代码枚举”的思路在竞赛和工程性能优化里反复出现。做题时不要急着上手写循环先在草稿纸上想清楚有没有可以剪枝的条件往往比优化循环体本身更有效。5. 递归判断字符串回文换个载体理解同一个本质数字回文搞清楚了字符串回文是同一个本质换了个壳。在C里字符串回文经常用来练递归因为递归的天然结构非常适合“从两头往中间收缩”的比较方式。递归思路非常简单判断一个字符串是否回文就是看首字符和尾字符是否相等如果相等再递归判断去掉首尾后的子串。#include string bool isPalindromeRecursive(const std::string s, int left, int right) { if (left right) return true; // 只剩0个或1个字符必然回文 if (s[left] ! s[right]) return false; return isPalindromeRecursive(s, left 1, right - 1); }调用方式就是isPalindromeRecursive(s, 0, s.size() - 1)。递归版和迭代版双指针的效率其实差不多差别主要在于递归会占用系统栈空间深度等于字符串长度的一半。如果字符串特别长比如几万个字符递归可能造成栈溢出而迭代版就没有这个问题。所以实际项目里我更推荐双指针迭代版递归版更适合用来理解“递归是什么”以及训练算法思维。这里顺带说一个经常考的变体不区分大小写、忽略非字母数字字符的回文判断。比如A man, a plan, a canal: Panama在忽略标点、空格和大小写的情况下是回文。实现时要先对字符做规范化处理#include cctype bool isAlphanumeric(char c) { return std::isalnum(static_castunsigned char(c)); } bool isPalindromeIgnoreNonAlpha(const std::string s) { int left 0, right s.size() - 1; while (left right) { while (left right !isAlphanumeric(s[left])) left; while (left right !isAlphanumeric(s[right])) right--; if (std::tolower(static_castunsigned char(s[left])) ! std::tolower(static_castunsigned char(s[right]))) { return false; } left; right--; } return true; }这里有一个C新手特别容易踩的坑std::tolower和std::isalnum的入参必须是unsigned char类型转换后的值不能直接传char。因为char在某些平台是有符号类型直接传负数进去会导致未定义行为。这个问题在ASCII纯英文场景下通常不会暴露但一旦字符串里含有高位字符就可能出现诡异的结果。稳妥写法就是像上面那样套上一层static_castunsigned char()。6. 回文数与进制转换十进制习惯之外的思维拓展很多人在学进制转换时会把“十进制下是回文”当成唯一标准这恰恰是思维定势。一个数在不同进制下的表示完全不同它是不是回文数也会随之改变。比如十进制数5在二进制下是101这是回文十进制数21在二进制下是10101也是回文但它在十进制下显然不是回文。这类题目的标准问法是判断一个十进制整数在二进制表示下是否为回文。解决思路分两步第一步把十进制数转换成二进制字符串第二步对字符串做回文判断。#include string #include algorithm std::string toBinaryString(int x) { if (x 0) return 0; std::string s; while (x 0) { s.push_back((x % 2) ? 1 : 0); x / 2; } std::reverse(s.begin(), s.end()); return s; } bool isBinaryPalindrome(int x) { std::string s toBinaryString(x); return isPalindromeRecursive(s, 0, s.size() - 1); }注意toBinaryString里每次取余得到的位是二进制的最低位所以先append到字符串末尾最后统一reverse才是正确的二进制表示。这个问题真正的难点往往不是字符串回文判断而是进制转换本身。很多初学者会把十进制转二进制的顺序搞反写出的字符串是反的导致回文判断结果完全错误。我建议在写这类代码时先用小数字手推一遍比如x 10二进制是1010不是回文x 9二进制是1001是回文。验证过代码输出再继续。由这个题目再延伸一步判断一个数在2到16的任意进制下是否为回文。思路完全一致只需要把x % 2改成x % base把1/0改成数字到字符的映射即可。这个扩展题很适合拿来检验自己是不是真的理解了进制转换的本质而不只是背代码。7. 从回文数到水仙花数一类经典枚举题的本质相通回文数之后很多教材会把水仙花数安排成进阶练习。所谓水仙花数是指一个n位数它的每个位上的数字的n次方之和等于它本身。比如153 1^3 5^3 3^3所以153是一个3位水仙花数。这个题和回文数有什么共同点它们都是“对数字结构做数学判定”的典型问题都需要熟练拆解每一位。区别在于回文数关注位与位之间的对称关系水仙花数关注每一位的幂次和。题目虽然不一样但核心循环结构非常像——都要用%10取末位、/10去掉末位来拆数字。#include cmath bool isNarcissistic(int n) { int temp n, sum 0; int digits std::to_string(n).size(); // 位数 while (temp 0) { int digit temp % 10; sum static_castint(std::pow(digit, digits)); temp / 10; } return sum n; }要提醒的是std::pow返回的是浮点数做幂运算后强转回整数在某些边缘情况下可能会有精度误差。比如std::pow(5, 3)理论上应该精确等于125但浮点表示偶尔会给出124.999999强转int后就变成124造成错误结果。稳妥做法是自己写一个整数幂函数用循环累乘实现int intPow(int base, int exp) { int result 1; for (int i 0; i exp; i) { result * base; } return result; }然后在上面的判断里把std::pow(digit, digits)换成intPow(digit, digits)这样就能完全避开浮点精度问题。水仙花数的枚举量限制也需要心里有数3位水仙花数有4个153、370、371、4074位有3个5位开始数量慢慢多起来。如果题目要求找出所有7位水仙花数暴力枚举从1000000到9999999需要做几百万次幂运算性能就会开始吃紧。这时候可以预先计算0到9的n次方表把幂运算缓存起来每位数字查表累加即可。这种“预处理查表”的优化思路跟前面回文数构造法里“枚举前半部分而非完整数字”的精神是一样的——先用数学或逻辑缩小计算规模再去写循环。实战心得我在给学生讲这些题目时最常强调的不是代码本身而是先判断数据范围再选择算法。数据范围小暴力永远是最快写对的方式数据范围一大就必须先寻找可剪枝的数学性质。养成这个习惯后你再看任何“经典例题”看到的就不是一堆孤立题目而是一整套可复用的解题策略。8. 把回文数知识点串起来一道综合训练题的完整拆解前面讲了判定、构造、质数、进制、递归、水仙花数每个知识点单独拿出来都不难但组合起来就非常考验综合运用能力。最后我给出一个能串联以上大部分内容的综合训练题你可以当成自测来做。题目统计1到100000之间十进制表示是回文数、且二进制表示也是回文数的数字个数。粗看这道题需要写一个十进制回文判定函数写一个进制转换函数得到二进制字符串写一个字符串回文判定函数遍历1到100000逐一判断。逐个函数分开写逻辑非常清晰#include iostream #include string int main() { int count 0; for (int i 1; i 100000; i) { // 十进制回文判定用上面的isPalindromeHalf或字符串法均可 if (!isPalindromeHalf(i)) continue; std::string binary toBinaryString(i); if (isPalindromeRecursive(binary, 0, binary.size() - 1)) { count; } } std::cout count std::endl; return 0; }也可以先转成字符串统一用双指针法判断代码更有整体感#include iostream #include string #include algorithm bool isPalindromeStr(const std::string s) { int left 0, right s.size() - 1; while (left right) { if (s[left] ! s[right]) return false; left; right--; } return true; } int main() { int count 0; for (int i 1; i 100000; i) { std::string decStr std::to_string(i); if (!isPalindromeStr(decStr)) continue; std::string binStr; int t i; while (t 0) { binStr.push_back((t % 2) ? 1 : 0); t / 2; } std::reverse(binStr.begin(), binStr.end()); if (isPalindromeStr(binStr)) count; } std::cout count std::endl; return 0; }这个综合训练题的妙处在于每一步用到的都是前面讲过的基础知识但组合起来考察了模块化思维你能否把一个复杂问题拆成几个简单函数你能否复用已有的判断逻辑你能否在遍历中合理安排判断顺序来减少无谓计算我在实际教学时发现能独立完成这道题的初学者基本已经具备解决中等难度信息学题目的框架能力了。我自己当年练回文数的时候最大的体会就是一道看起来简单的题真正吃透它需要同时掌握边界条件、溢出处理、字符串操作、数学性质应用这几个维度。如果你能把本文里这些例题都自己动手实现一遍并且能解释清楚每一段代码为什么这么写那你的C基础就已经比大多数停留在“照着敲一遍”阶段的初学者扎实很多了。