題目

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
D 500
M 1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1

1
2
3
Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2

1
2
3
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3

1
2
3
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

  • 1 <= s.length <= 15
  • s contains only the characters (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’).
  • It is guaranteed that s is a valid roman numeral in the range [1, 3999].

解釋題目

一般來說，羅馬數字是從大到小排列並相加，例如 XII = 10 + 1 + 1 = 12。
但有幾個特殊情況需要用「減法」表示：

  • I 可以放在 V (5) 和 X (10) 前面，表示 4（IV）和 9（IX）
  • X 可以放在 L (50) 和 C (100) 前面，表示 40（XL）和 90（XC）
  • C 可以放在 D (500) 和 M (1000) 前面，表示 400（CD）和 900（CM）
    所以遇到這些組合時，要用減法而不是加法。
    此題要跟據這些規則，把羅馬數字字串轉成正確的整數。

思路 (1)

  1. 一次看兩個字母，看有沒有需要用到減法的情況，看完後去看下一個組合。
  2. 用雙指針的方式，從右邊開始加總比較直觀。
  3. 一開始右指針是最後一位，左指針是倒數第二位。
  4. 一般來說: 左指針值 > 右指針的值
    • 若左指針值 < 右指針值，須用減法運算，一次算兩個值，然後左右指針向左移動 2 步。
    • 若左指針值 > 右指針值，直接累加右指針的值，然後左右指針向左移動 1 步。
  5. 雙指針用 while 比較好理解，但是要注意臨界點，當右指針走回到第一位時，迴圈結束。此時如果左指針是負的，要加上第一位的值。

程式碼 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def romanToInt(self, s: str) -> int:
        roman_dict = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        n = len(s)
        result = 0
        left = len(s) - 2
        right = len(s) - 1
        while right >= 0:
            if left < 0:
                result += roman_dict[s[right]]
                break
            if roman_dict[s[left]] < roman_dict[s[right]]:
                result += roman_dict[s[right]] - roman_dict[s[left]]
                left -= 2
                right -= 2
            else:
                result += roman_dict[s[right]]
                left -= 1
                right -= 1
        return result

思路 (2)

  1. 可以直接比較跟下一個字母的值
    • 如果 當下字母值 > 下一個字母值，則要「加上」當下字母值 => 一般情況
    • 如果 當下字母值 < 下一個字母值，則要「減去」當下字母值
  2. 用 zip 可以將兩個陣列分別迭代列出，zip 會匹配剛好的一對一數量，不足的不會匹配。
  3. 最後一位一定不會匹配到，所以要加上最後一位的值。

程式碼 (2)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def romanToInt(self, s: str) -> int:
        res = 0
        roman = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

        for a, b in zip(s, s[1:]):
            if roman[a] < roman[b]:
                res -= roman[a]
            else:
                res += roman[a]

        return res + roman[s[-1]]