康瑞部落

Roman to Integer

Given a roman numeral, convert it to an integer.

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

解题思路：

罗马数字转化成数字。一种方法是映射法，每一位（阿拉伯数字）的字符到阿拉伯数字的映射。如下所示：

class Solution {
public:
    int romanToInt(string s) {
        int result=0;
        
        map<string, int> m({
            {"M", 1000}, {"MM",2000}, {"MMM", 3000},
            {"C", 100}, {"CC", 200}, {"CCC", 300}, {"CD", 400}, {"D", 500}, {"DC", 600}, {"DCC", 700}, {"DCCC", 800}, {"CM", 900},
            {"X", 10}, {"XX", 20}, {"XXX", 30}, {"XL", 40}, {"L", 50}, {"LX", 60}, {"LXX", 70}, {"LXXX", 80}, {"XC", 90},
            {"I", 1}, {"II", 2}, {"III", 3}, {"IV", 4}, {"V", 5}, {"VI", 6}, {"VII", 7}, {"VIII", 8}, {"IX", 9}
        });
        
        int len=s.length();
        int end=0, start=0;
        string str;
        
        //找到千位
        while(s[end]=='M' && end<len){
            end++;
        }
        if(end!=start){
            str=s.substr(start, end-start);
            result += m[str];
            start=end;
        }
        
        //找到百位
        while((s[end]=='C'||s[end]=='M'||s[end]=='D') && end<len){
            end++;
        }
        if(end!=start){
            str=s.substr(start, end-start);
            result += m[str];
            start=end;
        }
        
        //找到十位
        while((s[end]=='X'||s[end]=='L'||s[end]=='C') && end<len){
            end++;
        }
        if(end!=start){
            str=s.substr(start, end-start);
            result += m[str];
            start=end;
        }
        
        //找到个位
        while((s[end]=='I'||s[end]=='V'||s[end]=='X') && end<len){
            end++;
        }
        if(end!=start){
            str=s.substr(start, end-start);
            result += m[str];
            start=end;
        }
        
        return result;
    }
};

上述比较麻烦，感觉自己是老黄牛。另外一种方法，从左往右观察罗马字符，若前一个字符转化为阿拉伯数字比后一个字符转化为阿拉伯数字大，则直接将前一个字符加到结果中，否则将后一个字符减去前一个字符的差加入到结果中。这种方法非常clever。

class Solution {
public:
    int romanToInt(string s) {
        int len=s.length();
        if(len==0){
            return 0;
        }
        
        int result=0;
        
        int lastNum = 0;
        
        for(int i=0; i<len; i++){
            int thisNum = c2n(s[i]);
            if(lastNum==0){
                lastNum=thisNum;
            }else if(lastNum<thisNum){
                result += thisNum - lastNum;
                lastNum=0;
            }else{
                result += lastNum;
                lastNum = thisNum;
            }
        }
        
        result += lastNum;
        
        
        return result;
    }
    
    int c2n(char c){
        switch(c){
            case 'I': return 1;  
            case 'V': return 5;  
            case 'X': return 10;  
            case 'L': return 50;  
            case 'C': return 100;  
            case 'D': return 500;  
            case 'M': return 1000;  
            default: return 0;  
        }
    }
};