13. 罗马数字转整数
题目描述
罗马数字由七个符号组成：I=1，V=5，X=10，L=50，C=100，D=500，M=1000。
一般写法是大的符号在左、小的在右，数值相加，比如 XII = 12，XXVII = 27。
有六种减法写法，小符号放在大符号左侧时用大数减小数：IV=4，IX=9，XL=40，XC=90，CD=400，CM=900。
输入一个罗马数字字符串 s，返回它代表的整数。
示例 1
输入：s = "III" 输出：3
解释：三个 I 相加得 3。
示例 2
输入：s = "LVIII" 输出：58
解释：L = 50，V = 5，III = 3，合计 58。
示例 3
输入：s = "MCMXCIV" 输出：1994
解释：M = 1000，CM = 900，XC = 90，IV = 4，合计 1994。
数据范围
1 <= s.length <= 15s只含字符I、V、X、L、C、D、M。s一定是合法的罗马数字，表示的值在[1, 3999]之间。- 输入遵守标准写法，不会出现
IL、IM这类跨位的减法；例如 49 写作XLIX，999 写作CMXCIX。
解题思路
从左到右看每个符号：如果它比右边一个符号小，它就是减法形式中被减的那一项，应该减去；否则加上。例如 CM：C < M，先减 100，再加 1000，得到 900。最后一个符号右边没有符号，总是加上。
为什么正确
处理完前 i 个符号后，ans 等于这些符号带符号贡献之和；负贡献总会在下一步被更大的正贡献抵消。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
比较的是“当前符号与右侧邻居”，而不是与左侧；如果想用左侧比较，就得在发现大符号时补减两倍的前一项，容易写错。另外访问 s[i+1] 前要先判断 i+1 没有越界。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def romanToInt(self, s: str) -> int:
val = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
ans = 0
for i, c in enumerate(s):
v = val[c]
if i + 1 < len(s) and v < val[s[i + 1]]:
ans -= v
else:
ans += v
return ansclass Solution {
public int romanToInt(String s) {
Map<Character, Integer> val = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
int ans = 0;
for (int i = 0; i < s.length(); i++) {
int v = val.get(s.charAt(i));
if (i + 1 < s.length() && v < val.get(s.charAt(i + 1))) {
ans -= v;
} else {
ans += v;
}
}
return ans;
}
}class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> val = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
int ans = 0;
for (int i = 0; i < (int)s.size(); i++) {
int v = val[s[i]];
if (i + 1 < (int)s.size() && v < val[s[i + 1]]) {
ans -= v;
} else {
ans += v;
}
}
return ans;
}
};func romanToInt(s string) int {
val := 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++ {
v := val[s[i]]
if i+1 < len(s) && v < val[s[i+1]] {
ans -= v
} else {
ans += v
}
}
return ans
}var romanToInt = function(s) {
const val = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
let ans = 0;
for (let i = 0; i < s.length; i++) {
const v = val[s[i]];
if (i + 1 < s.length && v < val[s[i + 1]]) {
ans -= v;
} else {
ans += v;
}
}
return ans;
};function romanToInt(s: string): number {
const val: Record<string, number> = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
let ans = 0;
for (let i = 0; i < s.length; i++) {
const v = val[s[i]];
if (i + 1 < s.length && v < val[s[i + 1]]) {
ans -= v;
} else {
ans += v;
}
}
return ans;
}