LeetCode 羅馬數 13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.

X can be placed before L (50) and C (100) to make 40 and 90.

C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3
Example 2:

Input: "IV"
Output: 4
Example 3:

Input: "IX"
Output: 9
Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
           

羅馬數的特征上面已經說明了，對應關系見最上面的表，羅馬數大小從左往右看。

但是

• I(1) 才能放在 V (5) 和 X (10)之前算成 4 和 9.
• X(10) 才能放在 L (50) 和 C (100)之前算成 40 和 90.
• C(100) 才能放在 D (500) 和 M (1000)之前算成 400 和 900.

  大家發現這個規則的規律沒有，

I和X前面最多隻能放一個I，如果想表達3，不是IIV而是III，想表達8，不是IIX而是VIII；同理L和C，D和M也是一樣的。

即左邊小的數不能連着超過一次。這個規律十分重要。如果左邊的羅馬數小于等于右邊的羅馬數，則是左邊羅馬數加上右邊羅馬數；如果左邊的羅馬數大于右邊的羅馬數,則用目前已經計算的值加上右邊大的羅馬數減去兩倍的左邊小的羅馬數（可以觀察上面的例子）。

  羅馬數實際上是字元串，首先我們必須周遊羅馬數，其次要知道每次周遊到的羅馬數對應的是數字幾，可以使用switch，也可以使用HashMap來存儲羅馬數與整數對應關系。

class Solution {
    public int romanToInt(String s) {
      Map<Character, Integer> map = new HashMap();
      map.put('I', 1);
      map.put('V', 5);
      map.put('X', 10);
      map.put('L', 50);
      map.put('C', 100);
      map.put('D', 500);
      map.put('M', 1000);
      
      char[] sc = s.toCharArray();
      int total = map.get(sc[0]);
      int pre = map.get(sc[0]);
      for(int i = 1; i < sc.length; i++) {
        int cur = map.get(sc[i]);
        
        if(cur <= pre) {
        	total += cur;
        } else {
        	total = total + cur - 2 * pre;
        } 
        pre = cur;
      }
      return total;
    }
}
           

上面的規律還有另外一種解釋：

羅馬數	字面值和真實值
IV	I+V=6 真實值為6-2=4
IX	I+X=11 真實值為11-2=9
XL	X+L=60 真實值為60-20=40
XC	X+C=110 真實值為110-20=90
CD	C+D=600 真實值為600-200=400
CM	C+M=1100 真實值為1100-200=900

即出現以上組合不論前面的值是多少，加上上面的組合都會先減去2，減去20，減去200。例如XIV是14，其實是等于X+I+V-2=16-2=14

class Solution {
    public int romanToInt(String s) {
         int sum=0;
        if(s.indexOf("IV")!=-1){sum-=2;}
        if(s.indexOf("IX")!=-1){sum-=2;}
        if(s.indexOf("XL")!=-1){sum-=20;}
        if(s.indexOf("XC")!=-1){sum-=20;}
        if(s.indexOf("CD")!=-1){sum-=200;}
        if(s.indexOf("CM")!=-1){sum-=200;}

        char c[]=s.toCharArray();
        int count=0;

       for(;count<=s.length()-1;count++){
           if(c[count]=='M') sum+=1000;
           if(c[count]=='D') sum+=500;
           if(c[count]=='C') sum+=100;
           if(c[count]=='L') sum+=50;
           if(c[count]=='X') sum+=10;
           if(c[count]=='V') sum+=5;
           if(c[count]=='I') sum+=1;

       }
       return sum;
    }
}