13. Roman to Integer (Easy) Facebook Microsoft Bloomberg Uber Yahoo

Given a roman numeral, convert it to an integer.

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

Solution 1: naive switch O(n); O(1) 虽然速度比HashMap快，但面试中不推荐这种写法

这题要将罗马数字字符串转为整数，先要知道罗马数字的表示方式，请查wikipedia。
对于这题，关键点就是要找到字符串中的“左小数+右大数”组合，比如CM，XC，遇到这种要将左小数减去。
然后要考虑的是从左往右遍历，还是从右往左。从右往左简单，遇到“左小数”，直接减去即可。
从左往右就稍复杂，需要将“左小数”减两次。

    /**
     * String, Math.
     * First need to know the letter to value mapping.
     * Then need to clarify whether the input string can mean negative, or there is only uppercase.
     * <p>
     * For each character from the end to front:
     * | Add the value to result according to the character.
     * | Only when for C=100 X=10 I=1, need to compare current number with 500, 50 and 5.
     * | If result is larger or equal, they mean negative values.
     * | Subtract them from result.
     */
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int res = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            switch (c) {
                case 'M':
                    res += 1000;
                    break;
                case 'D':
                    res += 500;
                    break;
                case 'C':
                    res += 100 * (res >= 500 ? -1 : 1); // For CD or CM.
                    break;
                case 'L':
                    res += 50;
                    break;
                case 'X':
                    res += 10 * (res >= 50 ? -1 : 1); // For XL or XC.
                    break;
                case 'V':
                    res += 5;
                    break;
                case 'I':
                    res += res >= 5 ? -1 : 1; // For IV or IX.
                    break;
                default:
                    break;
            }
        }
        return res;
    }

Solution 2: HashMap O(n); O(1) 从右往左

用map，代码简洁。

    public int romanToIntB(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        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);

        int res = 0;
        int pre = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int cur = map.get(s.charAt(i));
            if (pre > cur) {
                res -= cur;
            } else {
                res += cur;
            }
            pre = cur;
        }
        return res;
    }

Solution 3: HashMap O(n); O(1) 从左往右

    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        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);

        int res = 0;
        int pre = 0;
        for (int i = 0; i < s.length(); i++) {
            int cur = map.get(s.charAt(i));
            if (pre < cur) { //左 < 右
                res -= (2 * pre -cur); //因为之前多加了一次，所以要减2倍。
            } else {
                res += cur;
            }
            System.out.println(res);
            pre = cur;
        }
        return res;
    }