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, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X II. The number 27 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.

Example 1:

Input: s = “III” Output: 3 Explanation: III = 3. Example 2:

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

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

Constraints:

1 <= s.length <= 15 s contains only the characters (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’). It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Problem is simpler to solve by working the string from back to front and using a map.

思路

通常，罗马数字的中小数字在大数字的右侧。如果输入的字符串符合这种情况，则可以将每个字符视为单独的值，并累积每个字符对应的值。

例如 \texttt{XXVII}XXVII 可视作 \texttt{X} \texttt{X} \texttt{V} \texttt{I} \texttt{I}=10 10 5 1 1=27X X V I I=10 10 5 1 1=27。

如果大数字左侧有小数字，则需要根据规则减去小数字。在这种情况下，我们也可以将每个字符视为一个单独的值。如果一个数字右侧的数字比它大，则取反数字的符号。

例如 \texttt{XIV}XIV 可视作 \texttt{X}-\texttt{I} \texttt{V}=10-1 5=14X?I V=10?1 5=14。

class Solution { 
         private:     unordered_map<char, int> symbolValues = { 
                 { 
        'I', 1},         { 
        'V', 5},         { 
        'X', 10},         { 
        'L', 50},         { 
        'C', 100},         { 
        'D', 500},         { 
        'M', 1000},     };  public
       
        : 
        int 
        romanToInt
        (string s
        ) 
        { 
          
        int ans 
        = 
        0
        ; 
        int n 
        = s
        .
        length
        (
        )
        ; 
        for 
        (
        int i 
        = 
        0
        ; i 
        < n
        ; 
        ++i
        ) 
        { 
          
        int value 
        = symbolValues
        [s
        [i
        ]
        ]
        ; 
        if 
        (i 
        < n 
        - 
        1 
        && value 
        < symbolValues
        [s
        [i 
        + 
        1
        ]
        ]
        ) 
        { 
          ans 
        -= value
        ; 
        } 
        else 
        { 
          ans 
        += value
        ; 
        } 
        } 
        return ans
        ; 
        } 
        }
        ; 
       

复杂度分析

时间复杂度：O(n)O(n)，其中 nn 是字符串 ss 的长度。

空间复杂度：O(1)O(1)。

作者：LeetCode-Solution 链接：https://leetcode.cn/problems/roman-to-integer/solution/luo-ma-shu-zi-zhuan-zheng-shu-by-leetcod-w55p/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution { 
        
public:
    //通常情况下，罗马数字中小的数字在大的数字的右边
    //I， V， X， L，C，D 和 M。
    int romanToInt(string s) { 
        
        //建立映射关系
        unordered_map<char,int> hash = { 
        { 
        'I',1},{ 
        'V', 5},{ 
        'X', 10},{ 
        'L', 50},{ 
        'C', 100},{ 
        'D', 500},{ 
        'M', 1000}};
        //如果只有一个元素，直接返回对应值
        if(s.size()==1) return hash[s[0]];
        int sum = 0; //保存结果
        int i=0;
        for(;i<s.size()-1;i++){ 
        
            //如果当前字符比它后面的字符要大，说明不是特例
            if(hash[s[i]]>=hash[s[i+1]]){ 
        
                sum+=hash[s[i]]; //保存结果
            }
            //如果当前字符比它后面的字符小，说明是特例
            else{ 
        
                sum+=hash[s[i+1]]-hash[s[i]]; //用大的减去小的
                i++; //i先往后移动一位，再通过for循环往后移动，相当于移动两位
            }
        }
        //此时i指向最后一个字符s[s.size()-1]
        if(hash[s[i-1]]>=hash[s[i]]) sum+=hash[s[i]]; //如果是正常的，加上去即可
        //如果是特例，不用管了
        return sum;

    }
};

作者：traveller-lzx 链接：https://leetcode.cn/problems/roman-to-integer/solution/c-luo-ma-shu-zi-zhuan-zheng-shu-by-trave-0xb5/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。