1 題目描述

和上一題相反，將羅馬數字轉換成阿拉伯數字。

2 解法

2.1 我的作法

我一開始想的比較複雜，是想要使用while迴圈，從第一個字串與第二個字串開始比較，一般來說羅馬字是由大排到小，因此一但發現“前面” < "後面“ （由小到大），前面要當減數，否則就是加法。

大概是這種感覺：

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
31
32
33
class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        num_dic = {'M': 1000, 'D': 500, 'C': 100, 'L': 50, 'X': 10, 'V': 5, 'I': 1}
        left = 0
        right = left + 1
        sum = 0
        # 如果只有一個字元，直接加上
        if len(s) < 2:
            sum += num_dic[s[left]]
        else:
            while right < len(s):
                left_val = num_dic[s[left]]
                right_val = num_dic[s[right]]
                # 一但發現 left < right，就是減法
                if left_val < right_val:
                    sum += left_val * (-1)
                # 否則加法
                else:
                    sum += left_val

                left += 1
                right = left + 1
                
                # 如果 right 已經到底了，那麼就加上最後一個
                if right == len(s):
                    sum += right_val

        print(f'final={sum}')
        return sum

時間複雜度：O(n)

  • n 是輸入字浮串的長度，這個解法只需要一次迭代。

空間複雜度：O(1)

  • 固定空間：儲存字典 num_dic，這是固定的大小，包含 7 個元素。
  • 變量：變量 left、right 和 sum 使用固定的額外空間。
  • 函數沒有使用額外的空間來儲存與輸入大小相關的數據結構，因此空間複雜度為 O(1)

2.2 更簡潔

但是有更簡潔的寫法，概念一樣，但是不用while迴圈，直接用for迴圈就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def romanToInt(self, s):
    """
    :type s: str
    :rtype: int
    """
    num_dic = {'M': 1000, 'D': 500, 'C': 100, 'L': 50, 'X': 10, 'V': 5, 'I': 1}
    sum = 0
    for i in range(len(s)):
        # 關鍵是如果 i 已經到底的前一個，那麼就不用比較了，直接加上
        # -1 是為了讓 i+1 不會超過範圍
        if i < len(s) - 1 and num_dic[s[i]] < num_dic[s[i+1]]:
            sum += num_dic[s[i]] * (-1)
        else:
            sum += num_dic[s[i]]
    return sum

3 結論

這題感覺難度也不會很難，是可以自己想出來的。