跳到主要内容

13. 罗马数字转整数

题目描述​

给定一个罗马数字字符串，将其转换成对应的整数。

罗马数字由以下符号组成：

符号值
I1
V5
X10
L50
C100
D500
M1000

特殊减法规则：通常情况下，罗马数字从左到右依次相加。但若某个符号比它右侧的符号值小，则该符号要被减去而非相加。例如：

  • IV = 5 - 1 = 4
  • IX = 10 - 1 = 9
  • XL = 50 - 10 = 40
  • XC = 100 - 10 = 90
  • CD = 500 - 100 = 400
  • CM = 1000 - 100 = 900

示例：

  • 输入：s = "III" → 输出：3
  • 输入：s = "LVIII" → 输出：58（L=50, V=5, III=3）
  • 输入：s = "MCMXCIV" → 输出：1994

解题思路​

第一步：理解问题本质​

罗马数字的本质规则只有两条：

  1. 当前符号 >= 右侧符号：将当前符号的值加到结果中。
  2. 当前符号 < 右侧符号：将当前符号的值减去（因为构成了减法组合）。

理解这一点后，整个问题变成：从左到右遍历字符串，对每个字符判断它和右侧字符的大小关系，决定是加还是减。

第二步：暴力解法​

最直接的想法是把所有减法组合（IV、IX、XL 等）先用字符串替换处理掉，然后逐字符累加。

class Solution:
    def romanToInt(self, s: str) -> int:
        # 先处理所有减法特殊情况
        special = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
        roman_map = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

        ans = 0
        i = 0
        while i < len(s):
            # 先尝试匹配两字符组合
            if i + 1 < len(s) and s[i:i+2] in special:
                ans += special[s[i:i+2]]
                i += 2
            else:
                ans += roman_map[s[i]]
                i += 1
        return ans

这个方法可以工作，但需要维护两张映射表，逻辑稍显繁琐。

为何还能更简洁：减法规则的本质只是"当前值 < 右侧值时减去"，不需要单独枚举所有组合，可以用一次遍历统一处理。

第三步：最优解法​

只用一张哈希表，一次遍历完成。

核心思路：遍历每个字符，比较它与右侧字符的值：

  • 若 roman_map[s[i]] < roman_map[s[i+1]]：说明这是减法组合，减去 roman_map[s[i]]
  • 否则：加上 roman_map[s[i]]

最后一个字符没有右侧字符，必然是加法，上述逻辑天然正确（i+1 越界时走 else 分支）。

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_map = {"M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1}
        ans = 0
        n = len(s)
        for i in range(n):
            # 当前符号值小于右侧符号值，说明是减法组合，减去当前值
            if i + 1 < n and roman_map[s[i]] < roman_map[s[i + 1]]:
                ans -= roman_map[s[i]]
            else:
                ans += roman_map[s[i]]
        return ans

完整代码实现​

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_map = {"M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1}
        ans = 0
        n = len(s)
        for i in range(n):
            if i + 1 < n and roman_map[s[i]] < roman_map[s[i + 1]]:
                ans -= roman_map[s[i]]
            else:
                ans += roman_map[s[i]]
        return ans

示例推演​

以 s = "MCMXCIV" 为例，期望输出 1994。

索引字符当前值右侧值操作ans 累计
0M1000100(C)1000 >= 100，加1000
1C1001000(M)100 < 1000，减900
2M100010(X)1000 >= 10，加1900
3X10100(C)10 < 100，减1890
4C1001(I)100 >= 1，加1990
5I15(V)1 < 5，减1989
6V5无末尾，加1994

最终结果：1994，正确。

复杂度分析​

解法时间复杂度空间复杂度说明
暴力（字符串替换）O(n)O(n)需要额外空间存储中间字符串
最优（单次遍历）O(n)O(1)只用固定大小哈希表，原地计算

其中 n 为字符串长度。哈希表大小固定（7个键），视为 O(1) 空间。

易错点总结​

  1. 最后一个字符的处理：循环中 i + 1 < n 的判断保护了越界，最后一个字符必然走加法分支，逻辑天然正确，不需要单独处理。
  2. 减法判断方向：是"当前值 < 右侧值"时减去当前值，而不是"左侧值 < 当前值"时减去左侧值——两种写法等价，但要确保方向一致，不要混淆。
  3. 不需要枚举组合：不需要单独处理 IV、CM 等，统一的大小比较规则已经覆盖了所有情况。

扩展思考​

  • 反向题目：LeetCode 12「整数转罗马数字」，逻辑反过来，从大到小贪心选择罗马符号。
  • 本题核心：哈希表将字符映射到数值，配合一个简单的比较规则，把"看起来复杂"的减法规则化简为一个统一的判断条件，这是利用哈希表消除分支复杂度的典型应用。
加载评论中...