13. Roman to Integer

Posted on Edited on

题目

Given a roman numeral, convert it to an integer.

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

思路

罗马数字共有7个，即Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、Ⅼ（50）、Ⅽ（100）、Ⅾ（500）和Ⅿ（1000）。

  • 重复数次：一个罗马数字重复几次，就表示这个数的几倍。
  • 右加左减：
    • 在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
    • 在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
    • 左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
      但是，左减时不可跨越一个位值。比如，99不可以用IC（ {\displaystyle 100-1} 100-1）表示，而是用XCIX（ {\displaystyle [100-10]+[10-1]} [100-10]+[10-1]）表示。（等同于阿拉伯数字每位数字分别表示。）
    • 左减数字必须为一位，比如8写成VIII，而非IIX。
    • 右加数字不可连续超过三位，比如14写成XIV，而非XIIII。

参考自维基百科

所以从右往左依次读取每一个字符，比较他们的大小。如果右边一位字符的值大于当前字符的值，就在总结果里面减去当前的值，如果大于或等于当前的值就在总结果加上当前的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//C++
int romanToInt(string s) {
    map<char,int> romanMap = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int result = romanMap[s[s.size()-1]];
    for(int i = s.size()-2;i>=0;i--) {
        if(romanMap[s[i]]>=romanMap[s[i+1]]) {
            result+=romanMap[s[i]];
        }
        else {
            result-=romanMap[s[i]];
        }
    }
    return result;
}