題目

Seven different symbols represent Roman numerals with the following values:

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

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

  • If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.

  • If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).

  • Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.
    Given an integer, convert it to a Roman numeral.

  • 題目連結

Example 1

1
2
3
4
5
6
7
8
9
10
11
Input: num = 3749

Output: "MMMDCCXLIX"

Explanation:

3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC as 500 (D) + 100 (C) + 100 (C)
  40 = XL as 10 (X) less of 50 (L)
   9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2

1
2
3
4
5
6
7
8
Input: num = 58

Output: "LVIII"

Explanation:

50 = L
 8 = VIII

Example 3

1
2
3
4
5
6
7
8
9
10
Input: num = 1994

Output: "MCMXCIV"

Explanation:

1000 = M
 900 = CM
  90 = XC
   4 = IV

Constraints:

  • 1 <= num <= 3999

解釋題目

  1. 是第 13 題的相反過來。給你一個整數（範圍 1~3999），把它轉換成正確的羅馬數字表示法。

  2. 組成規則：

    • 羅馬數字是由大到小依序組合而成，例如 27 = XXVII（10+10+5+1+1）。
    • 但遇到 4 或 9 時，要用「減法」的方式表示，例如 4 = IV（5-1），9 = IX（10-1）。
    • 只有 I、X、C、M 這些 10 的倍數可以連續出現最多三次，像 III = 3、XXX = 30。
    • 5、50、500（V、L、D）不能連續出現。

  3. 遇到 4、9、40、90、400、900 這些數字時，要用減法（IV、IX、XL、XC、CD、CM）。

思路 (1)

  1. 這題有個重要關鍵，就是組成羅馬數字的所有組合只有13 個，所以可以全部列出來。
  2. 利用除法是不斷的減去的概念遍歷以上 13 組羅馬數字的組合。
  3. 由大值到小值依序遍歷，所以 要用陣列組合，才有順序，最後可求出羅馬數字。

程式碼 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def intToRoman(self, num: int) -> str:
        value_symbol_pairs = [
            (1000, 'M'),
            (900,  'CM'),
            (500,  'D'),
            (400,  'CD'),
            (100,  'C'),
            (90,   'XC'),
            (50,   'L'),
            (40,   'XL'),
            (10,   'X'),
            (9,    'IX'),
            (5,    'V'),
            (4,    'IV'),
            (1,    'I'),
        ]

        roman = ''
        for value, symbol in value_symbol_pairs:
            while num >= value:
                roman += symbol
                num -= value
        return roman