題目連結: Roman to Integer

題目描述為給定一字串，該字串為羅馬數字，要求將其轉換成阿拉伯數字，其中數字的範圍為[1,3999]。羅馬數字的表示法在題目連結中有說明 : 一般表示法為由大到小由左至右加起來，若小的數出現在比較大的數左邊時，則要減去比較小的數。

例子1: III=1+1+1=3。
例子2: IV=5-1=4。

思路1： 按照規則轉換

我們可以先建立一組對應關係(map)來轉換羅馬數字與阿拉伯數字。接下來我們從該字串 s 的最右邊開始處理數 tmep，並與前一次數字 last 做比較: 若 temp < last，則減去該數字，否則相加。直到遍歷完該字串。

• 複雜度評估
  如果輸入的字串長度 為 n ，則需要處理 n 次，時間複雜度為 O(n)。此方法有另外建立一組 map 來轉換羅馬數字與阿拉伯數字的關係，因為 map 存放大小為常數，與 n 無關，空間複雜度為 O(1)。

參考程式碼

var m=map[byte] int{
        'I' :    1,
        'V' :    5,
        'X' :    10,
        'L' :    50,
        'C' :    100,
        'D' :    500,
        'M' :    1000,
    }



func romanToInt(s string) int {
    sum:=0      
    temp:=0
    last:=0
    
    for i:=len(s)-1;i>=0;i--{
        temp=m[s[i]]
        sign:=1
        if(temp<last){
            sign=-1
        }
        
        sum=sum+(temp*sign)
        last=temp
    }
    
    return sum
    
}

小結

此題保證輸入的字串必為一組符合規則的羅馬數字，讓我們不必做判斷。另外此題也可以由字串最左邊開始處理，概念一樣，網路上的分享解法即採用此方式做。

我將解法加上簡單的測試，上傳程式碼到此。