题目描述

[EN | CN]

题目参考《LeetCode 12. 整数转罗马数字 ⌨️》。

解法 1:直接法

参考《LeetCode 12. 整数转罗马数字 ⌨️》,我们可以每次匹配前两个字符(因为有可能匹配到 IVIX 这种),如果不匹配的话再单独匹配一个字符。

假设罗马数字位度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def romanToInt(self, s: str) -> int:
        SYMBOLS = {'M': 1000, 'CM': 900, 'D': 500, 'CD': 400, 
                   'C': 100, 'XC': 90, 'L': 50, 'XL': 40, 
                   'X': 10, 'IX': 9, 'V': 5, 'IV': 4,
                   'I': 1}

        ret, i = 0, 0
        while i < len(s):
            if i < len(s) - 1 and s[i: i + 2] in SYMBOLS:
                ret += SYMBOLS[s[i: i + 2]]
                i += 2
            else:
                ret += SYMBOLS[s[i]]
                i += 1

        return ret
  • 执行用时:56 ms,在所有 Python3 提交中击败了 84.86% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 6.45% 的用户。