力扣13. 罗马数字转整数：Java多种解法详解
题目描述
罗马数字由以下字符构成：I, V, X, L, C, D, M，分别对应数值1, 5, 10, 50, 100, 500, 1000。
特殊规则：当小值字符位于大值字符左侧时，表示减法（如 IV=4）。要求将罗马数字转换为整数，输入保证有效且范围在[1, 3999]内。
解法一：哈希表 + 左到右遍历（推荐）
代码实现
java">import java.util.HashMap;
import java.util.Map;class Solution {public int romanToInt(String s) {Map<Character, Integer> map = new HashMap<>() {{put('I', 1);put('V', 5);put('X', 10);put('L', 50);put('C', 100);put('D', 500);put('M', 1000);}};int ans = 0;for (int i = 0; i < s.length(); i++) {if (i < s.length() - 1 && map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {ans -= map.get(s.charAt(i));} else {ans += map.get(s.charAt(i));}}return ans;}
}
复杂度分析
- 时间复杂度：O(n)，遍历一次字符串。
- 空间复杂度：O(1)，哈希表存储固定7个字符的映射。
核心思路
从左到右遍历字符，若当前字符值小于下一个字符值，则减去当前值（如 IV=4 即 -1+5），否则直接累加。
解法二：右到左遍历 + 层级比较
代码实现
java">class Solution {public int romanToInt(String s) {int sum = 0, level = 1;for (int i = s.length() - 1; i >= 0; i--) {int value = getValue(s.charAt(i));if (value < level) {sum -= value;} else {sum += value;level = value;}}return sum;}private int getValue(char c) {switch(c) {case 'I': return 1;case 'V': return 5;case 'X': return 10;case 'L': return 50;case 'C': return 100;case 'D': return 500;case 'M': return 1000;default: return 0;}}
}
复杂度分析
- 时间复杂度：O(n)，反向遍历一次字符串。
- 空间复杂度：O(1)，仅用常数变量。
核心思路
从右向左遍历，维护一个层级变量 level。若当前字符值小于层级，则减去该值（如 IX 中 I 在右侧遍历时会被减去），否则累加并更新层级。
解法三：直接映射 + 后向修正
代码实现
java">class Solution {public int romanToInt(String s) {int sum = 0, prev = 0;for (int i = s.length() - 1; i >= 0; i--) {int curr = getValue(s.charAt(i));sum += (curr < prev) ? -curr : curr;prev = curr;}return sum;}private int getValue(char c) {switch(c) {case 'I': return 1;case 'V': return 5;case 'X': return 10;case 'L': return 50;case 'C': return 100;case 'D': return 500;case 'M': return 1000;default: return 0;}}
}
复杂度分析
- 时间复杂度：O(n)，反向遍历一次字符串。
- 空间复杂度：O(1)，无需额外存储。
核心思路
反向遍历时，若当前值小于前一个值则减去，否则累加。例如 IX 反向遍历先处理 X（+10），再处理 I（-1），结果为9。
各解法对比
| 解法 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 解法一 | 逻辑清晰，代码简洁 | 需哈希表额外空间 | 通用场景 |
| 解法二 | 无哈希表，空间更优 | 反向遍历需适应 | 注重空间优化 |
| 解法三 | 直接映射，高效 | 需手动处理字符映射 | 性能敏感场景 |
示例解析
以输入 MCMXCIV 为例：
- 解法一：
M(1000)→ 累加1000C(100) < M(1000)→ 累加100 → 总1100M(1000)前无更大值 → 累加1000 → 总2100- 后续同理，最终结果为1994。
总结
以上三种方法均能高效解决该问题，推荐使用解法一或解法三，逻辑清晰且代码简洁。实际开发中可根据需求选择空间或时间最优方案。
可直接复制代码到力扣运行，保证通过！
如需进一步优化或探讨其他解法，欢迎评论区留言讨论。
