#13. Roman to Integer

題目描述

羅馬數字是由七種符號組成的I、V、X、L、C、D以及M。

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

舉例來說，2會使用II來表示，由兩個1組成。\ 12則表示成XII，簡單以X + II組成。\ 27則表示成XXVII，則是由XX + V + II`組成。\

羅馬數字通常以由大至小、由左至右的格式呈現。但是，數字4並不是IIII，而是表示成IV。1在5之前表示我們要將5減去1成為4。這個規則也用於數字9，表示成'IX'。總共有六個數字會以這個規則呈現：

I可以被放在V(5)和X(10)之間用來表示4和9。
X可以被放在L(50)和C(100)之間用來表示40和90。
C可以被放在D(500)和M(1000)之間用來表示400和900。

給你一個羅馬數字，把它轉換成整數。

限制條件

1 <= s.length <= 15
s只會由字元I、V、X、L、C、D、M組成。
s的範圍在[1, 3999]之間並且保證是符合羅馬數字格式的。

解題思路

Brute Force

最直覺的解決方式，就是把數字一個一個處理，先處裡特殊的組合IV、IX、XL、XC、CD、CM等，再處理可以被單個計算的I、V、X、L、C、D、M。

public class Solution { 
	public int RomanToInt(string s) {
        int ans = 0;
        for(int i=0;i<s.Length;i++){
            if(s[i]=='I' && i!=s.Length-1){                
                if(s[i+1]=='V'){
                    ans+=4;      
                    i++;                  
                }else if(s[i+1]=='X'){
                    ans+=9;
                    i++;
                }else{
                    ans+=1;
                }                
            }else if(s[i]=='X' && i!=s.Length-1){
                if(s[i+1]=='L'){
                    ans+=40;                 
                    i++;       
                }else if(s[i+1]=='C'){
                    ans+=90;
                    i++;
                }else{
                    ans+=10;
                } 
            }else if(s[i]=='C' && i!=s.Length-1){
                if(s[i+1]=='D'){
                    ans+=400;             
                    i++;           
                }else if(s[i+1]=='M'){
                    ans+=900;
                    i++;
                }else{
                    ans+=100;
                } 
            }else{
                switch(s[i]){
                    case 'I':
                        ans+=1;
                        break;
                    case 'V':
                        ans+=5;
                        break;
                    case 'X':
                        ans+=10;
                        break;
                    case 'L':
                        ans+=50;
                        break;
                    case 'C':
                        ans+=100;
                        break;
                    case 'D':
                        ans+=500;
                        break;
                    case 'M':
                        ans+=1000;
                        break;
                }
            }
        }
        return ans;
    }
}

複雜度分析：

時間複雜度：要檢查完所有字元，因此時間複雜度為O(n)。
空間複雜度：空間不會動態增加，因此空間複雜度為O(1)。

首先我們可以用Hash Table將羅馬字母直接對應到數值，減少寫錯的機會。
再來是判斷特殊組合的時候，是由i和i+1來判斷的，當兩者組成特殊組合的時候，再將數值轉換。但其實我們也可以將特殊組合視為兩個相減的單獨字元，同時因為一般的羅馬數字是由大到小、由左到右排序的，所以我們只要判斷i比i+1的數值來的小，就可以知道它是不是特殊組合，如果是特殊組合的話，先減去當前字元的數值，到下一個字元時再加上下一個字元的數值，就會等於特殊組合的數值了。

public class Solution { 
	public int RomanToInt(string s) {
        var ht = new Hashtable();        
        ht.Add('I',1);
        ht.Add('V',5);
        ht.Add('X',10);
        ht.Add('L',50);
        ht.Add('C',100);
        ht.Add('D',500);
        ht.Add('M',1000);        

        int ans = 0;
        for(int i=0;i<s.Length;i++){
            if(i<s.Length-1 && (int)ht[s[i]]<(int)ht[s[i+1]]){                
                ans-=(int)ht[s[i]];                
            }else{                
                ans+=(int)ht[s[i]];
            }
        }        
        return ans;        
    }
}