1 題目描述

把數字轉換成羅馬數字，正常情況就是把每個字母相加，並且大字母在前，小字母在後，上邊也介紹了像 4 和 9 那些特殊情況。

2 解法

2.1 我的作法(無HashTable)

簡單粗暴些，把所有可能都列舉出來，包含1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1，然後一個一個去減，直到 num 為 0 為止。

大概是這種感覺：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        arr = [(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')]
        ans = ""
        for key, val in arr:
            print(f'num={key}, val={val}')
            if num >= key:
                count = int(num / key)
                mud = num % key
                ans += count * val
                num = mud
                print(f'count={count}, mud={mud}, ans={ans}, num={num}')

        return ans

時間複雜度：O(1)

  • 循環次數：函數中有一個 for 循環，遍歷 arr 列表中的所有元素。arr 列表的長度是常數（13），所以這個循環的次數是固定的，為 13。
    空間複雜度：O(1)
  • 固定空間：儲存 arr 列表，這是固定的大小，包含 13 個元素。

3 結論

這題感覺難度應該是 easy ，沒有那麼難，就是理清楚題意，然後就可以往出列舉就行了。