LeetCode 13. 罗马数字转整数

题意

输入罗马数字，输出对应的整数。具体规则间题面。

思路

直接写。

由于两个字母结合的优先级高于一个字母的优先级，故我们可以把所有可能的情况存下来，然后遍历字符串时优先考虑两个字母的情况。时间复杂度$O(n)$。

代码

class Solution {
public:
    int romanToInt(string s) {

        string tmp;
        int res = 0, len = s.size();
        map<string, int> MP = {{"I",1},{"IV",4},{"V",5},{"IX",9},{"X",10},{"XL",40},{"L",50},{"XC",90},{"C",100},{"CD",400},{"D",500},{"CM",900},{"M",1000} };

        for(int i = 0; i < len; ++i)
        {
            tmp = s.substr(i, 2);
//            cout << tmp << ' ' << MP[tmp] << endl;
            if(MP[tmp])
            {
                res += MP[tmp];
                ++i;
            }
            else
            {
                tmp = s.substr(i, 1);
                res += MP[tmp];
            }
//            cout << res << endl;
        }
        return res;
    }
};

总结

借助map是慢了点（在所有运行时间中垫底的存在），但做法就这么个做法，可以直接多个if判断，没必要再写一遍了。