Leetcode - 13： 罗马数字转整数

罗马数字转整数

来源：LeetCode

标签：基础、哈希表

参考资料：

相似题目：

题目

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

样例1

输入: “III”
输出: 3

样例2

输入: “IV”
输出: 4

样例3

输入: “IX”
输出: 9

样例4

输入: “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.

样例5

输入: “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解题思路

主要思路是顺序遍历字符串，逐个字符的判断和处理。另外可以使用哈希表来存储所有最简的表示。

参考代码1

class Solution {
public:
    int romanToInt(string s) {
        int i=0;
        int ans=0;
        while(i<s.size()){
            switch(s[i]){
                case 'M': ans+=1000; break;
                case 'D': ans+=500; break;
                case 'C': 
                    if(i<s.size()-1 && (s[i+1]=='D' || s[i+1]=='M')) ans-=100;
                    else ans+=100;
                    break;
                case 'L': ans+=50; break;
                case 'X': 
                    if(i<s.size()-1 && (s[i+1]=='L' || s[i+1]=='C')) ans-=10;
                    else ans+=10;
                    break;
                case 'V': ans+=5; break;
                case 'I': 
                    if(i<s.size()-1 && (s[i+1]=='V' || s[i+1]=='X')) ans-=1;
                    else ans+=1;
                    break;
            }
            i++;
        }
        return ans;
    }
};

参考代码2

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<string, int> mymap;
        mymap["I"]=1;
        mymap["V"]=5;
        mymap["X"]=10;
        mymap["L"]=50;
        mymap["C"]=100;
        mymap["D"]=500;
        mymap["M"]=1000;
        mymap["IV"]=4; mymap["IX"]=9;
        mymap["XL"]=40; mymap["XC"]=90;
        mymap["CD"]=400; mymap["CM"]=900;
        
        int i=0;
        int ans=0;
        while(i<s.size()){
            if(mymap.find(s.substr(i,2))!=mymap.end()){
                ans+=mymap[s.substr(i,2)];
                i+=2;
            }
            else{
                ans+=mymap[s.substr(i,1)];
                ++i;
            }
        }
        return ans;
    }
};