013J. 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.

Best Method

这是我看过的最好的答案了。

• 首先从后往前 iteration 这样就从低位 到 高位

• 由于只有 I X C 会既放在前面也放在后面，所以除了这三个之外的字母 直接 sum += 就可以了

• 从后往前累加，考虑 I, 当累加小于5的时候，它的作用是+1，大于5则起到-1的作用。

• 以此类推 X 小于50 和 C 小于500.

• 特殊例子只有 IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900 非常容易验证

这是不可能更好的答案了

class Solution {
    public int romanToInt(String s) {
       int sum = 0;
        for(int i = s.length() - 1; i > -1; i -= 1) {
            char c = s.charAt(i);
            switch(c){
                case 'I':
                    sum += (sum >= 5 ? -1 : 1);
                    break;
                case 'V':
                    sum += 5;
                    break;
                case 'X':
                    sum += (sum >= 50 ? -10 : 10);
                    break;
                case 'L':
                    sum += 50;
                    break;
                case 'C':
                    sum += (sum >= 500 ? -100 : 100);
                    break;
                case 'D':
                    sum += 500;
                    break;
                case 'M':
                    sum += 1000;
                    break;
            }
        }
        return sum;
    }
}