LeetCode 随笔1-罗马数字转整数

罗马数字转整数

I = 1

V = 5

X = 10

L = 50

C = 100

D = 500

M = 1000

ps：小的数字在大的数字左边，则为大的数字减去左边的数字（只有I，X，C可以作为小的数字出现在大的数字前面），且只能在它们下一位和下下位字母的前面(I只能在V和X的前面，X只能在L和C的前面，C只能在D和M的前面)
e.g：4 = IV, 9 = IX, 40 = XL, 90 = XC
44 = XLIV, 99 = XCIX 而不是 IC, 49 = XLIX 而不是 IL

思路

字符组合最多只有13种组合，组合数确定且元素少，使用map能最快的匹配符号数字

class Solution {
public:
    int romanToInt(string s) {
        unordered_map <string,int> m = {{"I":1},
                                {"IV":3},
                                {"IX":8},
                                {"V":5},
                                {"X":10},
                                {"XL":30},
                                {"XC":80},
                                {"L":50},
                                {"C":100},
                                {"CD":300},
                                {"CM":800},
                                {"D":500},
                                {"M":1000}};
        int first = m[s.substr(0, 1)];
        for(int i=1; i<s.size(); ++i){
            string two = s.substr(i-1, 2);
            string one = s.substr(i, 1);
            first += m[two] ? m[two] : m[one];
        }
        return r;
    }
};

优化

IV,IX 定义为3，8，因为字符是++遍历，例如IV，先是遍历I=1，在遍历V=5，这里还需要判断IV是否匹配，匹配为4并删除之前的结果，这里需要处理之前得出的两个数字1和5，会过度操作且复杂，改为每次都会匹配当前位 以及 带上前一位组合的成的字符，如果匹配则留下两加，还是IV，首先I=1，加入总数，遍历+1，遍历V以及IV，IV存在则加入总数，则总数1+3=4，再例如XI，首先X=10，加入总数，遍历+1，遍历I以及XI，XI不存在，则I加入总数，10+1 = 11