LeetCode 0013 罗马数字转整数Roman to Integer哈希表与相邻字符比较的单遍扫描解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文基于仓库 articles/roman-to-integer.md 中的算法讲解系统梳理 LeetCode 0013「罗马数字转整数」的哈希表解法从左到右扫描字符串用当前字符小于下一字符则减、否则加这一条统一规则同时处理常规加法与减法记数法如 IV 4。仓库在 python/0013-roman-to-integer.py、cpp/0013-roman-to-integer.cpp、go/0013-roman-to-integer.go 等十余种语言目录下提供了可直接运行的实现。读完本文你将掌握该题的 O(n) 时间、O(1) 空间解法理解六种减法记数规则的本质并能规避两个最常见的边界错误。一、问题背景罗马数字的符号表与减法规则罗马数字由七个符号构成每个符号对应一个固定的整数值| 符号 | 值 | | ---- | -- | | I | 1 | | V | 5 | | X | 10 | | L | 50 | | C | 100 | | D | 500 | | M | 1000 |例如2写作II两个 1 相加12写作XIIX II27写作XXVIIXX V II。罗马数字通常从左到右按从大到小书写但存在六种特殊的**减法记数subtractive notation**情形——较小的符号放在较大的符号之前表示相减I可放在V5和X10之前构成 4 和 9X可放在L50和C100之前构成 40 和 90C可放在D500和M1000之前构成 400 和 900。例如MCMXCIV应解析为M 1000, CM 900, XC 90, IV 4结果共1994。这正是题目要求处理的核心难点。二、前置知识Prerequisites在动手实现之前需要具备以下三个基础能力Hash Map哈希表用于存储每个罗马数字字符对应的整数值实现 O(1) 查找字符串遍历String Iteration逐字符扫描字符串并在遍历过程中比较相邻元素条件逻辑Conditional Logic根据当前字符值与下一字符值的大小关系决定当前字符是加还是减。三、核心思想Intuition罗马数字的常规写法是从左到右累加。解题的关键洞察在于减法记数法的处理当一个较小的值出现在较大的值之前时如IV实际含义是相减而非相加IV 4而非I V 6。于是可以提炼出一条统一规则从左到右扫描时如果当前符号的值小于下一个符号的值就减去当前符号的值否则加上当前符号的值。这一条规则同时优雅地覆盖了普通加法与减法两种情况避免了为六种特殊组合单独写分支。以MCMXCIV为例逐步推演索引字符与下一字符比较动作累计结果0M(1000)1000 1000? 否100010001C(100)100 1000? 是-1009002M(1000)1000 10? 否100019003X(10)10 100? 是-1018904C(100)100 1? 否10019905I(1)1 5? 是-119896V(5)末尾无下一字符51994最终得到 1994与题目示例一致。四、算法步骤Algorithm创建哈希表为每个罗马数字字符I, V, X, L, C, D, M存储其对应的整数值将结果初始化为0遍历字符串中的每一个字符若当前字符的值小于下一字符的值则从结果中减去当前字符的值否则将当前字符的值加到结果中返回最终结果。注意第 3 步中与下一字符比较的动作在最后一个字符处必须跳过因为该字符没有后继只需直接累加即可。五、多语言实现完整代码以下实现与仓库源码一一对应可直接在各自语言的 LeetCode 环境中运行。Pythonclass Solution: def romanToInt(self, s: str) - int: roman { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 } res 0 for i in range(len(s)): if i 1 len(s) and roman[s[i]] roman[s[i 1]]: res - roman[s[i]] else: res roman[s[i]] return res与 python/0013-roman-to-integer.py 中的实现完全一致i 1 len(s)先做越界检查再访问s[i 1]避免了最后一个字符的索引越界。Javapublic class Solution { public int romanToInt(String s) { MapCharacter, Integer roman new HashMap(); roman.put(I, 1); roman.put(V, 5); roman.put(X, 10); roman.put(L, 50); roman.put(C, 100); roman.put(D, 500); roman.put(M, 1000); int res 0; for (int i 0; i s.length(); i) { if (i 1 s.length() roman.get(s.charAt(i)) roman.get(s.charAt(i 1))) { res - roman.get(s.charAt(i)); } else { res roman.get(s.charAt(i)); } } return res; } }Cclass Solution { public: int romanToInt(string s) { unordered_mapchar, int roman { {I, 1}, {V, 5}, {X, 10}, {L, 50}, {C, 100}, {D, 500}, {M, 1000} }; int res 0; for (int i 0; i s.size(); i) { if (i 1 s.size() roman[s[i]] roman[s[i 1]]) { res - roman[s[i]]; } else { res roman[s[i]]; } } return res; } };JavaScriptclass Solution { /** * param {string} s * return {number} */ romanToInt(s) { const roman { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000, }; let res 0; for (let i 0; i s.length; i) { if (i 1 s.length roman[s[i]] roman[s[i 1]]) { res - roman[s[i]]; } else { res roman[s[i]]; } } return res; } }C#public class Solution { public int RomanToInt(string s) { Dictionarychar, int roman new Dictionarychar, int { {I, 1}, {V, 5}, {X, 10}, {L, 50}, {C, 100}, {D, 500}, {M, 1000} }; int res 0; for (int i 0; i s.Length; i) { if (i 1 s.Length roman[s[i]] roman[s[i 1]]) { res - roman[s[i]]; } else { res roman[s[i]]; } } return res; } }Gofunc romanToInt(s string) int { roman : map[byte]int{ I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000, } res : 0 for i : 0; i len(s); i { if i1 len(s) roman[s[i]] roman[s[i1]] { res - roman[s[i]] } else { res roman[s[i]] } } return res }仓库中的 go/0013-roman-to-integer.go 即为上述实现其中map[byte]int以字节为键直接利用s[i]的byte类型完成查找。Kotlinclass Solution { fun romanToInt(s: String): Int { val roman mapOf( I to 1, V to 5, X to 10, L to 50, C to 100, D to 500, M to 1000 ) var res 0 for (i in s.indices) { if (i 1 s.length roman[s[i]]!! roman[s[i 1]]!!) { res - roman[s[i]]!! } else { res roman[s[i]]!! } } return res } }注意 Kotlin 中map[key]返回可空类型需要用!!断言非空由于输入保证只含七个合法罗马字符该断言是安全的。Swiftclass Solution { func romanToInt(_ s: String) - Int { let roman: [Character: Int] [ I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 ] let chars Array(s) var res 0 for i in 0..chars.count { if i 1 chars.count roman[chars[i]]! roman[chars[i 1]]! { res - roman[chars[i]]! } else { res roman[chars[i]]! } } return res } }Swift 中先通过Array(s)将字符串转为字符数组既方便按下标访问也保证了chars[i]与chars[i 1]的相邻比较语义正确。Rustimpl Solution { pub fn roman_to_int(s: String) - i32 { let roman |c: u8| - i32 { match c { bI 1, bV 5, bX 10, bL 50, bC 100, bD 500, bM 1000, _ 0, } }; let bytes s.as_bytes(); let mut res 0; for i in 0..bytes.len() { if i 1 bytes.len() roman(bytes[i]) roman(bytes[i 1]) { res - roman(bytes[i]); } else { res roman(bytes[i]); } } res } }Rust 版本将字符到值的映射写成闭包roman通过s.as_bytes()获得字节切片配合bI字节字面量匹配实现零堆分配的轻量查找。六、复杂度分析时间复杂度$O(n)$其中 $n$ 为输入字符串长度。每个字符只被访问常数次当前字符的查找与最多一次下一字符的比较哈希表查找本身为 O(1)。空间复杂度$O(1)$因为哈希表只包含固定的 7 个字符映射与输入规模无关。七、常见陷阱Common Pitfalls1. 总是相加而忽略减法记数最常见的错误是遍历时无条件累加每个罗马字符的值导致IV被算成I V 6而非V - I 4。修复方法即本文的核心规则比较当前字符与下一字符的值当前者较小时做减法。2. 相邻字符比较时的越界错误Off-by-One在判断当前字符是否小于下一字符时如果忘记验证i 1是否在字符串长度范围内会在访问s[i 1]时触发数组越界。必须始终先检查i 1 len(s)再进行访问——这一点在 articles/roman-to-integer.md 中被明确强调也是上述所有语言实现中if条件的标准写法。八、仓库源码中的其他实现变体仓库在 cpp/0013-roman-to-integer.cpp 等文件中提供了与文档思路一致但风格各异的实现可作为对比学习的素材。C 语言显式取出下一个值c/0013-roman-to-integer.c 将字符转值逻辑抽成value(char)辅助函数switch返回 1~1000非法字符返回 0。循环体内先取valueCurrent value(s[i])再判断(i 1) len有后继则取valueNext否则将valueNext置为0——这样末尾字符必然走累加分支从另一角度规避了越界问题。Java先加后修正仓库中的 java/0013-roman-to-integer.java 采用不同的等价写法不向前看而是向后看——若当前字符值大于前一字符值说明前一轮被多加了用result map.get(s.charAt(i)) - 2 * map.get(s.charAt(i - 1))完成修正先去掉之前多加的一次再补上减法语义。该变体同样得到正确结果展示了同一算法向前比较与向后修正两种视角。C用优先级函数比较相邻字符cpp/0013-roman-to-integer.cpp 额外维护了一个prec(char)优先级函数I→1, V→2, …, M→7当prec(s[i]) prec(s[i 1])时执行ans ans - val(s[i]) val(s[i 1])并跳过下一字符i相当于把相减的一对一次性合并处理。从源码结构看这种写法把比较与取值分离便于扩展到更多字符集。Rust从右向左的函数式写法rust/0013-roman-to-integer.rs 还提供了一种函数式变体roman_to_int_functional用s.chars().rfold(0, ...)从右向左折叠累加器acc已包含右侧子串的和因此只需判断当前字符是否小于其右侧已累积的量级如I在acc 5时取-1即可在单次折叠中完成全部计算无需索引与越界判断。九、验证与测试建议建议用以下几组用例覆盖常规加法、全部六种减法组合与混合场景输入预期输出覆盖点III3纯累加LVIII58常规混合L VIIIIV4减法1 在 5 前IX9减法1 在 10 前XL40减法10 在 50 前XC90减法10 在 100 前CD400减法100 在 500 前CM900减法100 在 1000 前MCMXCIV1994多种减法混合题目示例运行仓库中的对应实现如python/0013-roman-to-integer.py、go/0013-roman-to-integer.go、typescript/0013-roman-to-integer.ts即可验证上述用例全部通过。十、延伸阅读本解法与仓库中的 articles/integer-to-roman.md整数转罗马数字互为逆运算可对照学习贪心取值的思路哈希表查值的技巧在 articles/is-anagram.md、articles/two-integer-sum.md 等题目中同样适用。仓库 README.md 汇总了全部题解目录可按语言python/、java/、cpp/、go/、rust/等继续检索。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考