LeetCode 12 整数转罗马数字Integer to Roman全解贪心表驱动与数位查表两种解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 12Integer to Roman展开系统讲解如何将 13999 范围内的整数转换为罗马数字。文章以本仓库中的 articles/integer-to-roman.md 为核心骨架覆盖前置知识、贪心表驱动Math - I与数位查表Math - II两种解法、各主流语言的实现代码、复杂度分析以及常见陷阱并结合 python/0012-integer-to-roman.py 等仓库源码印证实际实现。读完本文你将掌握罗马数字的减法表示规则并能用任意语言写出简洁、可复用的转换函数。一、前置知识罗马数字系统与减法表示1.1 七个基本符号罗马数字由七个符号构成对应关系如下该表同样完整注释在仓库 cpp/0012-integer-to-roman.cpp 文件头部符号值I1V5X10L50C100D500M1000例如2 写作II两个 I 相加12 写作XIIX II27 写作XXVIIXX V II。罗马数字通常按从左到右、从大到小的顺序书写。1.2 减法表示Subtractive Notation4 不写作IIII而是写作IV因为 I 放在 V5之前表示 5 − 1 4。同理 9 写作IX。减法规则共有六种情况I可放在V(5) 和X(10) 之前表示 4 和 9X可放在L(50) 和C(100) 之前表示 40 和 90C可放在D(500) 和M(1000) 之前表示 400 和 900。于是完整的符号—值映射共有 13 对I(1)、IV(4)、V(5)、IX(9)、X(10)、XL(40)、L(50)、XC(90)、C(100)、CD(400)、D(500)、CM(900)、M(1000)1.3 题目约束与示例题目输入约束为1 num 3999千位最大为MMM。示例1994→MCMXCIV其分解为M 1000、CM 900、XC 90、IV 4。若你需要反向转换罗马数字转整数可参考仓库中的姊妹题文档 articles/roman-to-integer.md 及对应实现 python/0013-roman-to-integer.py。二、解法一贪心表驱动Math - I2.1 核心思路罗马数字本质上是用有限面值的符号去凑一个整数且书写顺序固定为从大到小。因此关键洞察是从大到小依次处理面值每次尽可能多地减去当前最大面值并追加对应符号。把减法组合IV、IX、XL、XC、CD、CM也放进面值表就能让 4、9、40、90、400、900 这些特殊数字被自然地处理而无需任何条件分支。2.2 算法步骤按升序建立符号—值对照表包含全部 13 对含减法组合从大到小遍历该表对每一对用整数除法num // val得到符号应出现的次数count将符号重复count次拼接到结果字符串并用取模num % val更新剩余数值返回拼接结果。2.3 多语言实现原文档给出了 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言版本这里保留核心几种并给出完整可运行代码。Pythonclass Solution: def intToRoman(self, num: int) - str: symList [ [I, 1], [IV, 4], [V, 5], [IX, 9], [X, 10], [XL, 40], [L, 50], [XC, 90], [C, 100], [CD, 400], [D, 500], [CM, 900], [M, 1000] ] res for sym, val in reversed(symList): count num // val if count: res sym * count num % val return resCclass Solution { public: string intToRoman(int num) { vectorpairstring, int symList { {I, 1}, {IV, 4}, {V, 5}, {IX, 9}, {X, 10}, {XL, 40}, {L, 50}, {XC, 90}, {C, 100}, {CD, 400}, {D, 500}, {CM, 900}, {M, 1000} }; string res ; for (int i symList.size() - 1; i 0; i--) { string sym symList[i].first; int val symList[i].second; int count num / val; if (count 0) { res.append(count, sym[0]); if (sym.size() 2) res.append(1, sym[1]); num % val; } } return res; } };JavaScriptclass Solution { /** * param {number} num * return {string} */ intToRoman(num) { const symList [ [I, 1], [IV, 4], [V, 5], [IX, 9], [X, 10], [XL, 40], [L, 50], [XC, 90], [C, 100], [CD, 400], [D, 500], [CM, 900], [M, 1000], ]; let res ; for (let i symList.length - 1; i 0; i--) { const [sym, val] symList[i]; let count Math.floor(num / val); if (count 0) { res sym.repeat(count); num % val; } } return res; } }JavaScript 中除法得到浮点数必须用Math.floor取整这是跨语言实现时最容易踩的坑之一。Rustimpl Solution { pub fn int_to_roman(num: i32) - String { let sym_list [ (I, 1), (IV, 4), (V, 5), (IX, 9), (X, 10), (XL, 40), (L, 50), (XC, 90), (C, 100), (CD, 400), (D, 500), (CM, 900), (M, 1000), ]; let mut num num; let mut res String::new(); for (sym, val) in sym_list.iter().rev() { let count num / val; for _ in 0..count { res.push_str(sym); } num % val; } res } }C#、Go、Kotlin、Swift 版本与原文档一致可对照原文档 articles/integer-to-roman.md 查阅。2.4 仓库源码印证仓库中的多数实现正是这一思路的直接落地python/0012-integer-to-roman.py 采用升序列表 reversed()逆序遍历并对num // val的结果做真值判断java/0012-integer-to-roman.java 将 13 个面值拆成vals与symbols两个平行数组用while (num vals[i])内层循环反复减面值并追加符号go/0012-integer-to-roman.go 使用定长数组[13]int/[13]string和strings.Builder高效拼接rust/0012-integer-to-roman.rs 与 Go 版本结构几乎一致印证了该算法的语言无关性。2.5 复杂度分析时间复杂度O(1)——面值表长度固定为 13与输入大小无关空间复杂度O(1)——只使用了常量大小的辅助结构结果字符串长度上限约为 15 个字符如MMMCMXCIX可视作常量。三、解法二数位查表Math - II3.1 核心思路由于输入被限制在 13999可以按数位千位、百位、十位、个位预计算出所有可能的罗马数字表示转换时只需提取每一位数字、查表、拼接即可。这是一种典型的以空间换时间、换简单性的策略几乎零运算代码可读性极强。3.2 算法步骤建立四个查表数组千位、M、MM、MMM百位、C、CC、CCC、CD、D、DC、DCC、DCCC、CM十位、X、XX、XXX、XL、L、LX、LXX、LXXX、XC个位、I、II、III、IV、V、VI、VII、VIII、IX用除法与取模提取每一位数字从对应数组按下标查得该位的罗马数字串按千位 → 百位 → 十位 → 个位顺序拼接并返回。3.3 多语言实现Pythonclass Solution: def intToRoman(self, num: int) - str: thousands [, M, MM, MMM] hundreds [, C, CC, CCC, CD, D, DC, DCC, DCCC, CM] tens [, X, XX, XXX, XL, L, LX, LXX, LXXX, XC] 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] )Javapublic 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]; } }Cclass 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]; } };JavaScriptclass Solution { /** * param {number} num * return {string} */ intToRoman(num) { const thousands [, M, MM, MMM]; const hundreds [, C, CC, CCC, CD, D, DC, DCC, DCCC, CM]; const tens [, X, XX, XXX, XL, L, LX, LXX, LXXX, XC]; const ones [, I, II, III, IV, V, VI, VII, VIII, IX]; return ( thousands[Math.floor(num / 1000)] hundreds[Math.floor((num % 1000) / 100)] tens[Math.floor((num % 100) / 10)] ones[num % 10] ); } }Rustimpl Solution { pub fn int_to_roman(num: i32) - String { let thousands [, M, MM, MMM]; let hundreds [, C, CC, CCC, CD, D, DC, DCC, DCCC, CM]; let tens [, X, XX, XXX, XL, L, LX, LXX, LXXX, XC]; let ones [, I, II, III, IV, V, VI, VII, VIII, IX]; format!( {}{}{}{}, thousands[(num / 1000) as usize], hundreds[((num % 1000) / 100) as usize], tens[((num % 100) / 10) as usize], ones[(num % 10) as usize] ) } }注意Rust 中数组下标需为usize类型因此索引处需要as usize显式转换参见 rust/0012-integer-to-roman.rs 的另一种两数组写法JavaScript 中num / 1000是浮点除法需要Math.floor取整。3.4 两种解法对比维度Math - I贪心表驱动Math - II数位查表核心思想从大到小反复减去最大面值按数位预计算后查表拼接数据结构13 对符号值4 个定长字符串数组特殊数字处理内建在面值表中天然覆盖内建在各数位数组中天然覆盖循环次数最多 13 轮常数次4 次查表代码风格通用、易迁移到任意语言更简洁直观、零复杂逻辑时间/空间O(1) / O(1)O(1) / O(1)两种方法均满足题目约束实际面试中可任选其一若追求极简可读性推荐数位查表若希望算法思想可推广例如处理任意面值系统的兑换问题则推荐贪心表驱动。四、常见陷阱Common Pitfalls4.1 遗漏减法组合罗马数字对 4、9、40、90、400、900 使用减法表示IV、IX、XL、XC、CD、CM。常见错误是只把七个基本符号I、V、X、L、C、D、M放进查找表然后用复杂的条件分支去处理减法场景——这样做既容易出错代码也难以维护。最干净的做法是从一开始就把全部 13 对符号—值放进查找表让表驱动算法自然消化掉减法逻辑。4.2 处理顺序错误构建罗马数字时必须从大到小处理面值。如果从小值开始处理、或顺序混乱会产生非法结果。例如处理 1994 时若先处理个位再处理千位就无法正确组合出MCMXCIV。这正是贪心表驱动解法中reversed(symList)/ 倒序索引的关键原因。4.3 除法与取模逻辑混淆计算某个符号应出现多少次时必须用整数除法得到次数再用取模得到剩余值。二者混用、或每轮忘记更新剩余数值都会导致输出错误甚至死循环。以 Python 实现为例正确顺序是count num // val # 先除得到符号重复次数 res sym * count num % val # 再模更新剩余数值4.4 语言相关的取整陷阱JavaScript / TypeScript/得到浮点数必须Math.floor参见 typescript/0012-integer-to-roman.ts 中Math.floor(num / map[key])的写法Rust数组下标要求usize需显式类型转换rust/0012-integer-to-roman.rs。五、仓库实现汇总与延伸阅读本仓库针对该题在 9 种语言中提供了可运行的实现均可作为参考python/0012-integer-to-roman.py升序表 reversed()逆序遍历java/0012-integer-to-roman.java双平行数组 内层 while 循环cpp/0012-integer-to-roman.cpp文件头部含完整题目与规则注释javascript/0012-integer-to-roman.js、typescript/0012-integer-to-roman.tsgo/0012-integer-to-roman.go、rust/0012-integer-to-roman.rskotlin/0012-integer-to-roman.kt延伸阅读建议反向问题罗马数字转整数articles/roman-to-integer.md实现见 python/0013-roman-to-integer.py项目整体题目索引与配套文档README.md。通过对比本仓库各语言实现可以直观看出贪心表驱动算法在固定面值系统下的通用性与简洁性这也是该题在面试中最被看重的核心能力——把规则建模为数据表用标准流程取代散乱的条件分支。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考