013 · Roman to Integer
My First Thoughts
第一眼看这道题，我想到的是：这是不是一个字典匹配游戏？
每个罗马字符都对应一个固定的数字：
在 Python 里，可以先用一个 dictionary 把这些关系存起来：
values = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
}接下来要判断的是：罗马数字到底是“左大右小”还是“左小右大”。
如果是左大右小，比如：
LVIII那看起来就可以直接把每个字符对应的值加起来：
50 + 5 + 1 + 1 + 1 = 58如果是左小右大，比如：
IV那就不是简单相加，而是要做减法：
5 - 1 = 4所以最开始我会想先判断整个字符串的方向，再决定怎么处理：
def roman_to_int_first_try(s: str) -> int:
values = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
}
if values[s[0]] > values[s[-1]]:
left_big_right_small = True
else:
left_big_right_small = False
result = 0
if left_big_right_small:
for char in s:
result += values[char]
else:
for char in s[:-1]:
result -= values[char]
result += values[s[-1]]
return result这个想法存在问题，主要是我对罗马数字的不熟悉，因为罗马数字不一定只有一个整体方向。
Why That Is Not Enough
这个初版想法能处理一些简单情况。
比如 LVIII 是整体左大右小，直接相加没问题。
IV 是整体左小右大，用前面减、最后加的方式也能得到 4。
真正的问题出现在这种更混合的数字里：
MCMXCIV它不是只有一个方向，而是加法和减法关系交替出现：
M C -> 左大右小
C M -> 左小右大
M X -> 左大右小
X C -> 左小右大
C I -> 左大右小
I V -> 左小右大如果只用 s[0] 和 s[-1] 判断整个字符串的方向：
values[s[0]] > values[s[-1]]这里会得到：
M > V
1000 > 5于是程序会认为整个字符串都是“左大右小”，然后把所有字符都加起来：
1000 + 100 + 1000 + 10 + 100 + 1 + 5 = 2216但正确答案是：
1994问题不是“方向判断”这个想法错了，而是这个方向不能只判断一次。
罗马数字里的减法关系是局部的。每次看当前字符时，不能只看整个字符串的开头和结尾，而要看它右边的下一个字符。
如果当前值小于右边的值，说明当前字符参与了减法形式，应该减去它。
否则，正常加上它。
Final Idea
从左到右遍历字符串。
对每个位置 i：
- 令
current表示s[i]的值 - 如果右边还有字符，令
next_value表示s[i + 1]的值 - 如果
current < next_value，把current从答案里减掉 - 否则，把
current加到答案里
以 MCMXCIV 为例：
M C M X C I V
1000 100 1000 10 100 1 5逐个判断：
M 后面是 C，1000 > 100，加 1000
C 后面是 M，100 < 1000，减 100
M 后面是 X，1000 > 10，加 1000
X 后面是 C，10 < 100，减 10
C 后面是 I，100 > 1，加 100
I 后面是 V，1 < 5，减 1
V 是最后一个，加 5结果：
1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994Why It Works
合法罗马数字中，减法形式只会表现为一个局部关系：左边的值比右边的值小。
因此不需要单独枚举 IV、IX、XL、XC、CD、CM。
只要在遍历时比较当前字符和下一个字符：
- 当前值小于下一个值时，当前值应该被减去
- 否则，当前值应该被加上
这样每个字符只处理一次，所有普通加法和特殊减法都能被同一个规则覆盖。
Code
def roman_to_int(s: str) -> int:
values = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
}
total = 0
for i in range(len(s)):
current = values[s[i]]
if i + 1 < len(s) and current < values[s[i + 1]]:
total -= current
else:
total += current
return totalComplexity
| Time | \(O(n)\) — 每个字符只遍历一次 |
| Space | \(O(1)\) — 映射表大小固定 |
Takeaway
当一个规则看起来有很多特殊情况时，先找它们共同的局部特征。这道题里，所有减法形式都可以归纳成同一件事：当前值小于右边的值时，当前值要被减掉。
← Quiz