[LeetCode] Roman to Integer 羅馬數字轉化成整數

連結： https://leetcode.com/problems/roman-to-integer/#/description

難度：Easy

題目：13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

翻譯：将給定的羅馬數字轉化為整數，輸入保證在1～3999之間

概念：什麼是羅馬數字？

羅馬數字共有7個，即Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、Ⅼ（50）、Ⅽ（100）、Ⅾ（500）和Ⅿ（1000）。按照下述的規則可以表示任意正整數。需要注意的是羅馬數字中沒有“0”，與進位制無關。一般認為羅馬數字隻用來記數，而不作演算。

重複數次：一個羅馬數字重複幾次，就表示這個數的幾倍。

右加左減：在較大的羅馬數字的右邊記上較小的羅馬數字，表示大數字加小數字。

在較大的羅馬數字的左邊記上較小的羅馬數字，表示大數字減小數字。

左減的數字有限制，僅限于I、X、C。比如45不可以寫成VL，隻能是XLV。但是，左減時不可跨越一個位值。

左減數字必須為一位，比如8寫成VIII，而非IIX。

右加數字不可連續超過三位，比如14寫成XIV，而非XIIII。

數位限制：同一數位最多隻能連續出現三次，如40不可表示為XXXX，而要表示為XL。等

——維基百科

tips: 3999範圍内的羅馬數字不會用到加上劃線的字母

思路：從最後一個字元開始，如果目前字元對應的數字比上一個數字小，那麼就把結果減去目前字元對應的數字，否則加上目前字元對應數字。為了處理邊界情況，在原字元串最後添加一個字元，該字元是原來的尾字元。

參考代碼：

Java

public class Solution {
    public int romanToInt(String s) {
        if(s==null || s.length()==0)
            return 0;
        Map<Character, Integer> m = new HashMap<Character, Integer>();
        m.put('I',1);
        m.put('V',5);
        m.put('X',10);
        m.put('L',50);
        m.put('C', 100);
        m.put('D', 500);
        m.put('M', 1000);
        
        int length = s.length();
        int result = m.get(s.charAt(length-1));
        for (int i=length-2; i>=0; i--){
            if(m.get(s.charAt(i))<m.get(s.charAt(i+1)))
                result -= m.get(s.charAt(i));
            else
                result += m.get(s.charAt(i));
        }
        return result;
    }
}