中心对称数判定：从月赛题到双指针与映射表实战

1. 从一道月赛题看中心对称数的判定逻辑第一次看到中心对称数这个名词很多人会下意识联想到回文数——毕竟对称两个字太容易让人往左右镜像的方向想。但中心对称数strobogrammatic number和回文数是两个完全不同的概念混淆它们几乎是每个初学者都会踩的第一个坑。这道来自2020年9月某地区计算机学会月赛丙组T2的题目核心就是让选手判断一个数字在旋转180度之后是否和原来看起来一样。它考察的不是复杂算法而是对数字字形旋转关系的建模能力以及边界情况的处理耐心。我把这类题归为规则映射型问题你不需要动态规划、不需要图论只需要把每个数字旋转后的形态搞清楚再按位比对即可。听起来简单但真正动手写的时候0和6、6和9、8和8、1和1、9和6这几组关系一旦记混或者对前导零、单位数、非法字符的处理不到位就会在测试点上一片飘红。这道题适合刚接触C字符串处理和模拟题的选手练手也适合作为如何把生活规则翻译成代码的教学案例。下面我会从题目本质、字形映射的建模、逐位判定的实现、以及月赛现场最容易翻车的几个细节完整拆一遍。所有代码和思路都基于这道题最常见的输入输出约定来展开如果你手上有类似旋转后是否相同的变体题这套分析框架同样能直接套用。2. 中心对称数到底在判什么先把规则说透2.1 旋转180度不是镜像翻转很多人第一反应是把字符串倒过来比较这是回文数的做法。中心对称数的操作是把整个数字旋转180度。旋转之后原来的最低位会跑到最高位同时每个数字本身的字形也会发生变化。所以判定条件包含两个动作的叠加——位置反转加上字形变换。举个最直观的例子69。把69旋转180度6转到个位变成99转到十位变成6结果是69和原来一样所以69是中心对称数。再看96旋转后6到十位、9到个位得到69和96不等所以96不是。这两个例子放在一起看就能明白为什么不能简单反转字符串——反转69得到96但正确答案是它对称反转96得到69但正确答案是它不对称。位置反转只是必要条件的一半字形变换才是决定性的另一半。2.2 哪些数字旋转后还是合法数字这是整道题的地基。在常见的七段数码管或印刷体字形下0、1、8旋转180度后还是自己6旋转后变成99旋转后变成62、3、4、5、7旋转后不再是合法数字。所以合法的旋转映射只有五组原数字旋转180度后0011698896只要数字里出现了2、3、4、5、7中的任意一个这个数就绝对不可能是中心对称数可以直接判否。这个结论能帮你在代码里做一次快速剪枝省掉后面的逐位比对。注意不同题目对字形的约定可能略有差异比如有的题把2也算作可旋转在特定字体下2旋转后像2但这道月赛题采用的是最标准的五组映射。做题前一定要看清题目对数字字形的说明不要凭自己的想象扩展映射表。2.3 长度奇偶带来的中心位约束当数字长度为奇数时正中间那一位旋转180度后必须还是它自己因为它在旋转中位置不变第i位旋转后还是第i位。中间位能自我对称的数字只有0、1、8三个。6和9不行——它们旋转后会互换放在正中间就会导致旋转前后不一致。比如619旋转后是619吗6变9、1不变、9变6得到916不等。而818旋转后还是818成立。这个约束是很多选手容易忽略的他们写循环时只比对了对称位置却没单独检查奇数长度的中心位。如果中心位是6或9对称位置比对可能全部通过但整体结果仍然是错的。所以判定逻辑里必须显式处理中心位。3. 把字形规则翻译成代码映射表与判定骨架3.1 用数组做O(1)映射查询最直接的建模方式是用一个长度为10的数组下标是原数字值是对应的旋转结果非法数字标记为-1int rot[10] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};这样查一个数字c的旋转结果就是rot[c - 0]常数时间代码也干净。相比写一堆if-else或者switch数组映射在模拟题里几乎是最优解——可读性好扩展映射也只需要改数组。我见过有选手用mapchar,char来做功能上没问题但常数大、代码还长月赛这种追求稳定和速度的场合没必要。3.2 双指针从两端向中间夹判定主体用双指针最自然左指针i从0开始右指针j从n-1开始每次检查s[i]旋转后是否等于s[j]同时s[j]旋转后是否等于s[i]。其实由于映射是双向的6和9互为逆只检查一个方向也能推出另一个方向但为了逻辑清晰、防止映射表写错两个方向都查一遍更稳妥。bool check(const string s) { int i 0, j (int)s.size() - 1; while (i j) { int a rot[s[i] - 0]; int b rot[s[j] - 0]; if (a -1 || b -1) return false; if (a ! s[j] - 0 || b ! s[i] - 0) return false; i; j--; } return true; }当i和j相遇奇数长度或交错偶数长度时循环结束。相遇那一轮ij检查的是s[i]旋转后是否等于它自己这正好覆盖了中心位约束——不需要额外写特判。这是双指针写法的一个巧妙之处中心位检查被自然地融进了循环条件i j里。如果写成i j中心位就被跳过了奇数长度的6和9会漏判。3.3 为什么先做非法字符剪枝虽然上面的check函数在遇到非法数字时会返回false但在主流程里提前扫一遍、发现2/3/4/5/7就直接输出否定能省掉双指针的完整遍历。对于这道题的数据规模省不省这点时间无所谓但从工程习惯上讲先做廉价的前置校验、再做昂贵的完整判定是值得养成的思维。尤其是当题目有多组测试数据时剪枝的收益会累积。4. 月赛现场最容易翻车的五个细节4.1 前导零题目到底允不允许这是这道题争议最大的地方。如果输入是0它是中心对称数吗按映射0旋转还是0成立。如果输入是00呢旋转后还是00按纯字符串判定也成立。但00作为数字其实等于0很多题目会规定数字没有前导零或者输入保证是合法数字表示。我的处理原则是严格按题目对输入格式的说明来。如果题目说输入是一个整数那通常不会有前导零除非输入就是单个0如果题目说输入是一个数字字符串那就要考虑前导零是否合法。这道月赛题在常见版本里输入是一个非负整数所以前导零基本不会出现但0本身必须判为成立。我在代码里对0单独走一遍逻辑确保它不会被某些边界条件误杀。提示如果题目没有明确说不含前导零而你又拿不准最稳的做法是把判定写成纯字符串逻辑让00这种输入也按字形规则得出结果而不是自作主张去掉前导零。去掉前导零反而可能改变答案。4.2 单位数0、1、8成立6和9不成立长度为1时中心位就是它自己。0、1、8旋转后还是自己成立6旋转后是9不等于6不成立9同理。很多选手在写双指针时用了i j导致单位数直接返回true把6和9也判成了成立。这个bug在样例里不一定暴露但测试点里一定有单位数的6和9。4.3 字符与数字的转换别写反s[i] - 0得到的是数字值用来查rot数组rot[...]得到的是数字值要和s[j] - 0比较而不是和s[j]字符比较。我见过有选手写成if (rot[s[i]-0] ! s[j])字符和整数比较结果永远不等或者依赖ASCII码碰巧相等调试半天找不到原因。这类错误在模拟题里特别常见因为字符和数字在C里可以隐式转换编译器不报错运行时才出问题。4.4 映射表下标越界如果输入里混入了非数字字符虽然题目通常保证是数字s[i] - 0可能得到负数或大于9的值直接查rot数组就越界了。稳妥的做法是在查表前判断字符是否是数字或者把rot数组开大一点、对越界下标做保护。月赛题一般不会给非法字符但养成防御性编程的习惯没坏处。4.5 多组数据的初始化如果题目是多组测试T组每组的字符串要重新读入不要复用上一组的变量导致残留。用string s; cin s;在循环内声明天然避免这个问题。如果用全局数组存字符串记得每组清空。5. 从判定到举一反三这类题的通用拆解套路5.1 先画映射表再写代码凡是涉及变换后是否相同的题第一步永远是把变换规则穷举成一张表。中心对称数是五组映射换成旋转90度、镜像翻转、大小写互换也是同样的套路——先把每个元素变换后的结果列清楚代码只是表的翻译。很多选手一上来就写循环边写边想规则结果映射记混、边界漏掉。先花两分钟把表画在草稿纸上后面写代码会快得多也更不容易错。5.2 双指针是对称类判定的通用骨架回文、中心对称、镜像对称判定骨架几乎都是双指针从两端向中间夹。区别只在于比对的内容回文比的是字符相等中心对称比的是旋转后相等。把骨架和规则分离骨架复用、规则替换这类题就变成填空题了。我在训练时会让选手先写一个通用的双指针框架再把不同的比对函数塞进去练几次之后形成肌肉记忆。5.3 边界情况清单化每次做完一道模拟题我都会列一张边界清单空输入、单位数、全零、含非法字符、奇数长度中心位、偶数长度、最大长度。中心对称数这道题至少覆盖单位数、奇数中心位、非法数字三类边界。把清单固化成习惯比赛时按清单过一遍能挡掉大部分非算法性的失分。5.4 用暴力对拍验证如果对自己的判定没把握可以写一个暴力版本枚举所有可能的旋转结果和原串比较。对于小长度比如长度不超过6暴力枚举所有数字组合和你的双指针版本对拍几百组数据跑下来就能确认逻辑是否正确。对拍是月赛前最值得投入的调试手段比盯着代码看有效得多。6. 完整参考实现与逐行注释把上面的分析落成一份可直接提交的代码。输入约定按一个非负整数字符串处理输出是或否具体输出格式以题目为准这里用布尔返回值演示#include bits/stdc.h using namespace std; // 旋转180度映射下标为原数字值为旋转后数字-1表示非法 int rot[10] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6}; bool isStrobogrammatic(const string s) { // 前置剪枝出现非法数字直接判否 for (char c : s) { if (c 0 || c 9) return false; if (rot[c - 0] -1) return false; } int i 0, j (int)s.size() - 1; while (i j) { int a rot[s[i] - 0]; // 左位旋转结果 int b rot[s[j] - 0]; // 右位旋转结果 if (a ! s[j] - 0) return false; if (b ! s[i] - 0) return false; i; j--; } return true; } int main() { string s; cin s; cout (isStrobogrammatic(s) ? Yes : No) endl; return 0; }几个值得说明的点前置剪枝那层循环同时做了字符合法性检查和映射合法性检查一举两得双指针用i j保证奇数中心位被检查两个方向的比对都写出来虽然理论上冗余但能防止映射表笔误导致的单向错误。如果题目要求多组输入把main里的读入包一层while (cin s)或者按T循环即可。实测下来这份代码在长度到10^5级别的字符串上也能瞬间跑完因为每个字符最多被访问常数次整体O(n)。对于月赛丙组的T2难度这个复杂度绰绰有余。7. 我在这道题上踩过的坑与给后来者的建议我第一次做中心对称数时栽在了69和96的区分上。当时想当然地写了字符串反转比较样例里恰好只给了69这种对称的例子跑过了就以为对了结果提交后一半测试点WA。后来把96手动代进去才发现反转比较根本不成立——反转96得到69但正确答案是不对称。这个教训让我明白样例通过不等于逻辑正确一定要自己构造反例。第二个坑是奇数长度的中心位。我一开始写while (i j)单位数和奇数长度的中心位全被跳过6和9在中心位时误判为成立。改成i j之后问题消失但当时我花了很久才定位到是循环条件的问题因为代码看起来很对称、很合理。这提醒我双指针的循环边界条件要根据是否要检查中心位来决定不能无脑套i j。给正在练这类题的朋友一个建议每做完一道模拟题把映射规则、边界清单、易错点写成三行笔记。中心对称数这道题的笔记就是五组映射、中心位只能018、非法数字先剪枝。积累几十道之后你会发现模拟题的套路高度重合比赛时看到新题能快速归类把精力留给真正需要思考的部分。这道题本身不难但它把规则建模、边界处理、双指针骨架三个基本功揉在了一起作为丙组T2的练手题性价比很高。