Roman to Integer 419

Question

Given a roman numeral, convert it to an integer.

The answer is guaranteed to be within the range from 1 to 3999.

Symbol I V X L C D M

Value 1 5 10 50 100 500 1,000

Example

IV -> 4

XII -> 12

XXI -> 21

XCIX -> 99

Solution

罗马数字和阿拉伯数字转化，用一个map来保存之前的对应关系。同时要考虑几种特殊情况比如IV,IX, XL, XC, CD, CM。

方法一：从后往前把罗马数字表示的数加起来，只要考虑两种情况：

1. 如果当前位比后面一位小，则表示出现上面说的那几个特殊情况，因此要将当前位表示的数减去

2. 如果当前位比后面一位大或者相等，则直接加上当前位表示的数即可

方法二：我们也可以每次跟前面的数字比较，如果小于等于前面的数字，我们先加上当前的数字，如果大于的前面的数字，我们加上当前的数字减去二倍前面的数字，这样可以把在上一个循环多加数减掉。代码类似与第一种方法。

代码如下：

public class Solution {
    /**
     * @param s Roman representation
     * @return an integer
     */
    public int romanToInt(String s) {
        // Write your code here
        if(s == null || s.length() == 0){
            return 0;
        }

        int n = s.length();
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        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);

        int res = map.get(s.charAt(n - 1));
        for(int i = n - 2; i >= 0; i--){
            if(map.get(s.charAt(i + 1)) <= map.get(s.charAt(i))){
                res += map.get(s.charAt(i));
            }else{
                res -= map.get(s.charAt(i));
            }
        }

        return res;
    }
}