LeetCode 13. 罗马数字转整数
目录
题目描述
题意分析
输入一个罗马数字字符串，输出它代表的十进制整数。字符表只有七个：
I为 $1$，V为 $5$，X为 $10$，L为 $50$，C为 $100$，D为 $500$，M为 $1000$。书写规则的默认形态是从大到小依次排列、逐位相加，例如
XXVII就是 $10 + 10 + 5 + 1 + 1 = 27$。真正需要处理的是六种减法形式：IV为 $4$、IX为 $9$、XL为 $40$、XC为 $90$、CD为 $400$、CM为 $900$。它们的共同特征是一个较小的字符出现在较大的字符左边，此时这两个字符要合起来看作「大减小」。约束给得很宽厚：字符串长度在 $1$ 到 $15$ 之间，题目保证输入是合法罗马数字，取值范围在 $1$ 到 $3999$。合法性由题目兜底，意味着不必校验诸如
IIII、IC这类非法写法，也不会出现空串；数值上界 $3999$ 说明结果绝不会溢出，用int就够。边界只有两处：字符串仅一个字符时没有右邻居；以及扫描到最后一个字符时同样没有右邻居。两处其实是同一件事，处理方式必须一致。
解法：相邻值比较累加
核心思路
罗马数字通常从大到小排列，直接相加即可；减法组合的共同特征是左边字符的值小于右边字符，例如
IV可写成 $-1 + 5$，CM可写成 $-100 + 1000$。因此无需枚举六种组合，只需比较相邻字符。从左向右扫描：若当前值
cur小于右邻值next，将cur从答案中减去；否则将其加上。最后一个字符没有右邻，令next = 0，它会自然进入加法分支。不变量是：处理到位置 $i$ 后，
ans等于前缀中各字符按上述正负规则得到的贡献和。合法罗马数字中，升序相邻对恰好是减法组合；其左值取负、右值照常取正，合计就是组合真实值，因此扫描结束时得到整串数值。
解题步骤
- 建立七个罗马字符到整数的映射。
- 遍历字符串，读取当前值；有右邻时读取右邻值，否则取 $0$。
- 若
cur < next则减去cur，否则加上cur。- 遍历完成后返回累计结果。
以
MCMXCIV为例，各字符贡献依次为 $1000,-100,1000,-10,100,-1,5$，总和为 $1994$。纯加法串LVIII则依次累加 $50,5,1,1,1$，得到 $58$。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public int romanToInt(String s) {
Map<Character, Integer> value = new HashMap<>();
value.put('I', 1);
value.put('V', 5);
value.put('X', 10);
value.put('L', 50);
value.put('C', 100);
value.put('D', 500);
value.put('M', 1000);
int ans = 0;
for (int i = 0; i < s.length(); i++) {
int cur = value.get(s.charAt(i));
int next = i + 1 < s.length() ? value.get(s.charAt(i + 1)) : 0;
ans += cur < next ? -cur : cur;
}
return ans;
}
}
func romanToInt(s string) int {
value := map[byte]int{
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
ans := 0
for i := 0; i < len(s); i++ {
cur := value[s[i]]
next := 0
if i+1 < len(s) {
next = value[s[i+1]]
}
if cur < next {
ans -= cur
} else {
ans += cur
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每个字符只处理一次。
- 空间复杂度：$O(1)$，映射表固定只有七项。
关键点总结
- 合法罗马数字中，当前值小于右邻值时，当前位才是减法组合的左半部分。
- 比较必须使用严格小于；
II、XX等相同字符仍然相加。- 末位右邻值设为 $0$，可统一处理最后一个字符。
- 面试时应能说明：局部比较为什么等价于枚举
IV、IX等六种组合。
易错点总结
- 无条件累加会把
IV算成 $6$，而不是 $4$。- 写成
cur <= next会把II的第一个I错误减去，结果变成 $0$。- 直接读取
s[i + 1]会在最后一轮越界，必须判断边界或使用哨兵。- 比较字符编码而非映射后的数值会出错，例如
XL的字符编码顺序并不代表 $10 < 50$。- 该方法以输入合法为前提，不要额外套用“字符必须始终非升序”之类的错误校验。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 12. 整数转罗马数字 | 中等 | 反向构造与贪心取值 |
| 8. 字符串转换整数 (atoi) | 中等 | 字符串解析与边界处理 |
| 171. Excel 表列序号 | 简单 | 字母到进制数的转换 |
| 168. Excel 表列名称 | 简单 | 数值反解为字母序列 |
| 273. 整数转换英文表示 | 困难 | 数值分段映射为词组 |
| 405. 数字转换为十六进制数 | 简单 | 进制转换与符号处理 |