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 結論

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