题目描述

给定一个罗马数字，将其转换成整数。输入确保在 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

(模拟) $O(n)$

没啥算法成分，遍历 + 模拟。

时间复杂度

遍历字符串一次，时间复杂度为$O(n)$

参考文献

C++ 代码

class Solution {
private:
    unordered_map<char, int> c2num = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
public:
    int romanToInt(string s) {
        if (s.empty()) return 0;
        int res = 0, i = s.size() - 1;
        while (i >= 0){
            if (i >= 1 && c2num[s[i]] > c2num[s[i - 1]]) 
                res += c2num[s[i]] - c2num[s[i - 1]], i -= 2;
            else 
                res += c2num[s[i]], i -= 1;
        }

        return res;
    }
};