R / Richie全部文章 ↑

Python · 3 分钟阅读

13：罗马数字转整数

目录

题目

罗马数字包含以下七种字符：I、V、X、L、C、D 和 M。给定一个罗马数字，
将其转换成整数。

字符值

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

特殊规则（减法）

通常罗马数字中 小的数字在大的数字右边表示相加。但也有 6 种特例（小的数字在
大的数字左边表示相减）：

组合 数值 含义
IV 4 5 - 1
IX 9 10 - 1
XL 40 50 - 10
XC 90 100 - 10
CD 400 500 - 100
CM 900 1000 - 100

示例

输入: s = "III"
输出: 3

输入: s = "LVIII"
输出: 58
解释: L(50) + V(5) + III(3) = 58

输入: s = "MCMXCIV"
输出: 1994

约束

  • 1 <= s.length <= 15
  • s 仅含字符 I, V, X, L, C, D, M
  • 题目数据保证 s 是 有效的罗马数字，且表示范围 [1, 3999]

思路

把规则统一为一句话：从左到右遍历，若当前字符代表的值 < 下一个字符，则减去当前
值；否则加上当前值。最后再加上最后一个字符即可。

镜像地也可以 从右向左：维护 prev，当前值 < prev 就减，否则加。

方法一：从左到右

class Solution:
    def romanToInt(self, s: str) -> int:
        values = {"I": 1, "V": 5, "X": 10, "L": 50,
                  "C": 100, "D": 500, "M": 1000}
        total = 0
        n = len(s)

        for i in range(n - 1):
            if values[s[i]] < values[s[i + 1]]:
                total -= values[s[i]]
            else:
                total += values[s[i]]

        return total + values[s[-1]]

复杂度

  • 时间：O(n)，n 为字符串长度。
  • 空间：O(1)。

方法二：从右到左（推荐，更不易出错）

class Solution:
    def romanToInt(self, s: str) -> int:
        values = {"I": 1, "V": 5, "X": 10, "L": 50,
                  "C": 100, "D": 500, "M": 1000}
        total = 0
        prev = 0

        for ch in reversed(s):
            cur = values[ch]
            # 当前值比"前一个已处理值"小，就该减；否则加
            if cur < prev:
                total -= cur
            else:
                total += cur
            prev = cur

        return total

为什么不容易出错？循环里只看 当前值 与 前一个已处理的值，每个字符只
被访问一次，逻辑对称。

方法三：把特例也写到映射里（最直观）

class Solution:
    def romanToInt(self, s: str) -> int:
        # 提前把两字符的特例也列出来，匹配优先
        table = {
            "IV": 4, "IX": 9,
            "XL": 40, "XC": 90,
            "CD": 400, "CM": 900,
            "I": 1, "V": 5, "X": 10,
            "L": 50, "C": 100, "D": 500, "M": 1000,
        }

        i = total = 0
        while i < len(s):
            # 优先匹配两字符组合
            if i + 1 < len(s) and s[i:i + 2] in table:
                total += table[s[i:i + 2]]
                i += 2
            else:
                total += table[s[i]]
                i += 1
        return total

复杂度

  • 时间：O(n)。
  • 空间：O(1)（映射大小固定为 13）。

测试用例

def test():
    s = Solution()
    assert s.romanToInt("III") == 3
    assert s.romanToInt("LVIII") == 58
    assert s.romanToInt("MCMXCIV") == 1994
    assert s.romanToInt("IV") == 4
    assert s.romanToInt("XL") == 40
    assert s.romanToInt("CD") == 400
    assert s.romanToInt("MMMDCCCLXXXVIII") == 3888
    print("all passed")


test()

方法比较

方法 思路 代码量 可读性 推荐
方法一 左 → 右，加减交替 较短 中等 ★★
方法二 右 → 左，标准模板 较短 较好 ★★★
方法三 把特例写进映射 略长 最直观 ★★

易错点

  • 不要漏掉最后一个字符（方法一）。for i in range(n-1) 只处理了 n-1 个，
    所以要 + values[s[-1]]。
  • 不要对特例重复加：方法一里 IV 的处理是“I 减 1，V 加 5”，自然合成 4。
    不要先加 1 又加 5。
  • 输入保证是 有效罗马数字（且 ≤ 3999），所以不需要额外校验。