做力扣题有个规律——很多看起来“基础”的中等题恰恰是最练基本功的地方。第12题“整数转罗马数字”就是典型代表。这题不涉及高深的算法也不考复杂的C语法但它同时考察三样东西你对领域规则罗马数字的建模能力、对贪心思想的理解程度、以及代码落地时的边界意识。今天把这题从头到尾拆一遍从最直观的贪心解法讲到查表法再把我自己刷这道题时踩过的坑、调试记录和验证方法都摊开来说。无论你是刚刷题的新手还是准备面试想快速过中档题的老手都能从中拿到点能直接用的东西。1. 题目到底在考什么1.1 先把罗马数字规则彻底理清罗马数字不是单纯的进制转换它有一套自己的别扭规则。基本符号一共七个I代表1V代表5X代表10L代表50C代表100D代表500M代表1000。通常情况下罗马数字是从大到小排列书写的比如3写作III13写作XIII58写作LVIII50 5 3。但如果所有数字都只靠从大到小拼接就没法表达4、9这类数字了。罗马数字的解决办法是“减法原则”当一个较小的符号出现在较大符号的左侧时表示两者相减。于是4写作IV5减19写作IX10减1。这个原则同样作用于十位和百位40写作XL50减1090写作XC100减10400写作CD500减100900写作CM1000减100。题目明确限制输入范围是1到3999这个约束非常重要——它锁死了问题的规模也意味着M最多出现三次不需要考虑5000以上的表示法。也正是这个范围限制让这道题的所有解法都能做到常数级复杂度。如果把范围扩大到几万甚至更大问题性质就变了得另想办法。1.2 真正的难点只有六种特殊组合把规则捋完你会发现真正需要特殊处理的不是那几个基本符号而是六个“减法组合”4、9、40、90、400、900。我把它们整理成一张表后面对照用。数字罗马数字拆解逻辑4IV5 - 19IX10 - 140XL50 - 1090XC100 - 10400CD500 - 100900CM1000 - 100我一开始刷这道题的时候第一反应是“把数字拆成个十百千位每个位单独映射”。这个思路没错但直接实现会发现一个关键问题1994这种数百位是900十位是90个位是4这三个都不是基本符号必须用组合符号CM、XC、IV来表达。所以拆位没错但拆完之后你手里拿的映射表必须是完整的13个键值对不是7个。换句话说这题的本质是将整数映射到一组“符号值”其中包含7个基础符号和6个组合符号。想清楚这一点解法思路就打开了。2. 贪心解法最符合直觉的写法2.1 贪心策略的思考过程既然罗马数字的书写习惯是从大到小那么最自然的转换策略就是每次选当前数字能使用的最大符号值追加对应符号然后从数字里减去这个值重复直到数字归零。这个策略在算法里叫贪心。为什么贪心在这里成立这是很多人忽略的问题。关键在于符号值集合是“可加的”而且不存在“跳过较大值反而能得到更优表示”的情况。举个例子对任意一个大于等于1000的数先放一个M永远不会亏因为M就是最大的单位你不可能通过不放M、改用多个其他符号组合出更简洁的结果。同理遇到900到999之间的数直接用CM900开头就是最优的因为其他表达方式要么符号数更多要么不符合罗马数字规范。贪心能成立的根因在于这个13个符号的值集合足够“稀疏”每个数字的罗马表示是唯一确定的不存在歧义分支。明白了这一点写代码就顺理成章了。把13个键值对按值从大到小排好逐个尝试能减就减。2.2 完整C实现代码class Solution { public: string intToRoman(int num) { int values[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; string symbols[] {M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I}; string result; for (int i 0; i 13; i) { while (num values[i]) { result symbols[i]; num - values[i]; } } return result; } };这段代码最需要注意的地方是数组的排列顺序1000、900、500、400这种“一个大的配一个减法组合”的交错排列。我见过有人写成1000、500、400、900结果数字一遇到900就直接错误。顺序错了贪心就失效了。另外循环里的while而不是if很关键——数字可能是3000需要连续追加三个M用if只能追加一次。2.3 复杂度与正确性分析时间复杂度是O(1)values数组固定13个元素循环次数与输入规模无关。严格来说每个数字最多追加的字符次数有上限3999对应MMMCMXCIX共15个字符所以就算把字符串拼接算进去也是严格常数级。空间复杂度同样是O(1)只用了固定大小的数组和一个结果字符串。判断正确性有一个很直接的验证方法你随便挑几个数比如1994手动模拟一遍。num是1994先比较1000减一次result是Mnum变994接着比较900减一次result是MCMnum变94再比较90result是MCMXCnum变4最后比较4result是MCMXCIVnum归零结束。整个过程完全符合罗马数字规范。3. 查表法面试官更认可的另一种标准答案3.1 拆位映射的核心思路贪心解法虽然简洁但还有一个思路更直接也更适合面试时展示你对“空间换时间”的理解把数字按千位、百位、十位、个位拆开每一位分别查表。拆位的数学基础很简单num / 1000得到千位数字num % 1000 / 100得到百位数字num % 100 / 10得到十位数字num % 10得到个位数字。每个位上的数字范围都是0到9只要提前把每个位的0到9对应的罗马数字写进数组拼起来就是答案。这个方案的好处是完全不用考虑“减法原则”的实现逻辑因为规则已经被编码进表里了。比如百位的数组下标4对应CD下标9对应CM你在建表的时候就已经把特殊组合处理掉了。对读代码的人来说查表法的可读性比贪心更好一眼就能看懂映射关系。3.2 完整C实现代码class Solution { public: string intToRoman(int num) { string thousands[] {, M, MM, MMM}; string hundreds[] {, C, CC, CCC, CD, D, DC, DCC, DCCC, CM}; string tens[] {, X, XX, XXX, XL, L, LX, LXX, LXXX, XC}; string ones[] {, I, II, III, IV, V, VI, VII, VIII, IX}; return thousands[num / 1000] hundreds[num % 1000 / 100] tens[num % 100 / 10] ones[num % 10]; } };写这个代码有个细节坑百位的表里下标1到3是C、CC、CCC下标4是CD下标5是D下标6到8是DC、DCC、DCCC下标9是CM。很多人容易把下标4和9的位置写混或者漏掉空字符串。空字符串是关键——因为0在罗马数字里没有对应符号进位为0时该位必须返回空串否则整个结果就多出无用字符。数组下标从0开始正好用空串占住0号位置这个设计是被刻意安排的。3.3 两种解法的对比分析对比维度贪心法查表法核心思想每次选最大可用符号拆位后查预置表代码行数约10行约6行含表可读性依赖数组顺序需理解贪心逻辑映射关系一目了然时间复杂度O(1)O(1)空间复杂度O(1)O(1)扩展难度增加符号需改两个数组增加位需新建行数组从我实际面试的经验来看这两种写法面试官都认。但如果你时间允许我建议优先给贪心解法因为它在讲解时能把“为什么贪心成立”这个加分点带出来讲完再补一句“其实也可以用查表法”顺手展示第二种写法会让面试官觉得你对这道题的掌握是全方位的。4. 我刷这道题踩过的坑4.1 坑一把4和9当成普通字符硬拼我第一次写这题时想的是“把数字拆成4个位每个位用switch生成对应的I、V、X字符串最后拼起来”。结果在个位等于4的时候我输出的还是IIII等当时代码跑测试用例发现4应该是IV我才意识到6个减法组合必须作为一个整体单元处理不能拆开。这个坑的本质是“规则建模不完整”——你只用7个基础符号建模却忘了罗马数字系统里有13个有效符号。4.2 坑二值表顺序写反导致全军覆没贪心解法里values数组的顺序直接决定结果正确性。我试过把900排在1000前面结果数字是1900时程序先减900再减1000输出CMCM1000被拆成了900100正确结果应该是MCM。这个错误特别隐蔽因为单看某个局部步骤每个操作都有道理但全局顺序错了。排查方法是打一个日志打印每一步的num和追加的symbol立刻能看出顺序问题。4.3 坑三用switch写13个分支又长又容易漏有人喜欢用switch-case逐值判断也不是不行但13个分支写下来代码非常臃肿而且容易漏掉CM这类组合。我看过一份代码case 4和case 9覆盖了case 40和case 90忘了最后跑测试用例全崩。我的建议是能查表就查表能用数组就数组switch适合分支逻辑复杂但数量少的情况不适合这种“值到字符串”的纯映射。4.4 坑四查表法里下标计算错误查表法的常见错误集中在取余和整除的优先级上。我第一次写的时候写成了hundreds[num % 1000 / 100]这个其实是对的因为%和/优先级相同从左到右结合先算num % 1000再除以100。但有人会写成hundreds[num / 100 % 10]这个在百位上是等价的可一旦套用到十位就容易出错。更稳妥的做法是加括号明确意图hundreds[(num / 100) % 10]既不容易出歧义别人读代码也省心。5. 边界测试用例与验证方法5.1 必测的用例清单刷题时提交一次过固然开心但我建议在提交前自己先跑一遍这批用例能拦住大部分低级错误。输入期望输出覆盖点1I最小值边界4IV个位减法组合9IX个位减法组合40XL十位减法组合90XC十位减法组合400CD百位减法组合900CM百位减法组合58LVIII纯累加场景1994MCMXCIV多位混合场景3999MMMCMXCIX最大值边界5.2 验证思路与自测技巧手工验证1994这个用例最能说明问题。1994拆成1000 900 90 4对应符号是M CM XC IV拼接为MCMXCIV。这是力扣官方示例里最容易出错的一个因为同时涉及三个不同位上的减法组合。如果你用贪心法跑这个用例代码会依次匹配1000、900、90、4顺序完全符合罗马数字的书写规范。我还发现一个实用自测技巧把结果反着解析一遍来验证。比如你得到MCMXCIV按符号从大到小依次解析M是1000CM是900XC是90IV是4累加正好是1994。如果你写的转换函数能通过所有正向用例再反向校验一遍正确率基本就稳了。力扣第13题正好是“罗马数字转整数”两道题互为逆运算刷完第12题顺手把第13也做了等于白赚一个验证工具。6. 从这道题延伸出的实战思考6.1 贪心思想在什么情况下才靠谱这道题能这么轻松地使用贪心是因为罗马数字的13个符号值构成了一个“完全覆盖”的表示系统——任何1到3999的整数都有且仅有一种合法表示且较大符号永远优先。这个前提在现实工程里并不总是成立。比如货币找零问题里如果有面值25、20、5、1的硬币贪心找零在某些金额下就不是最优解。所以每当你打算用贪心先问自己一句局部最优是否真的能推出全局最优这道题能是因为符号值之间存在明确的整除层次关系不存在需要跨层级搭配的场景。6.2 建表思维才是这题最大的收获老实说这题的算法含量在力扣里只能算中下但它对工程实践的启发不小。现实中很多“格式转换”问题——数字转中文大写、时间戳转日期、状态码转描述文本——本质都是“规则建模 查表”。与其写一堆if-else或switch分支不如把规则整理成数组或哈希表用数据驱动逻辑。这题里的查表法就是这个思路的浓缩版。我后来在好几个项目里都用了类似的“预置映射表”方案代码可读性提升非常明显出bug的概率也低得多。6.3 我的个人刷题习惯分享最后分享一个我自己的习惯每道题AC之后我会把官方题解和排名靠前的评论区解法都看一遍重点看有没有比我的解法更简洁的思路。第12题我第一次用的是贪心AC之后看到查表法当时觉得很惊艳——因为查表法把“特殊情况”变成了“表项”根本不需要在逻辑里特判。从那以后我做字符串转换类的题目都会先想想能不能建表。这个习惯帮我养成了“先建模、再写码”的思维方式。如果你也正在刷力扣建议试试这个方法刷题数量和代码质量并不总是成正比的方法论比数量重要得多。
