13. Roman to Integer

發表於 更新於 分類於 ， 閱讀次數： Disqus： 文章字數： 229

種類 : string
難度 : easy
題目 : 13.Roman to Integer

思維邏輯

  1. 使用dict創建字母對應的數字
  2. 由左至右相加(e.g. XI = 5 + 1)
  3. 若當前的字母比次一個小, 則為負值(e.g. IX = -1 + 5)

解法

1
2
3
4
5
6
7
8
9
10
dict_roman = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}
roman = 0
s = "MCMIX"
for i in range(len(s)-1):
    if(dict_roman[s[i]] < dict_roman[s[i+1]]):
        roman = roman - dict_roman[s[i]]
    else:
        roman = roman + dict_roman[s[i]]
roman = roman + dict_roman[s[-1]]
print("roman=", roman)

難點

  1. 迴圈需要控制在倒數第二個字母停止，方便與最後一個字母做比較(e.g. IX)
  2. 最後要記得將最後一個字母值加入

最佳解法

Hash Table in python

1
2
3
4
5
6
7
8
9
10
class Solution:
    def romanToInt(self, s: str) -> int:
        roman={"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
        number=0
        for i in range(len(s)-1):
            if roman[s[i]] < roman[s[(i+1)]]:
                number-=roman[s[i]]
            else:
                number+=roman[s[i]]
        return number+roman[s[-1]]