分析

• 本题的考点：字符串、哈希表。

• 阿拉伯数字与罗马数字对应关系如下表：

• 这一题相当于Leetcode 0012 整数转罗马数字的逆运算。

• 观察可以发现，这里只有4、9比较特殊，其余只需将字母对应的值加到结果中即可。对于4、9对应的罗马数字，有两位，且前一位代表的数字小于后一位，因此当遇到一个字母代表的数字小于后一个字母时，减去当前字母代表的值即可，否则加上对一个值。如下图：

代码

• C++

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

        unordered_map<char, int> hash;
        hash['I'] = 1; hash['V'] = 5;
        hash['X'] = 10, hash['L'] = 50;
        hash['C'] = 100, hash['D'] = 500;
        hash['M'] = 1000;

        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            if (i + 1 < s.size() && hash[s[i]] < hash[s[i + 1]]) res -= hash[s[i]];
            else res += hash[s[i]];
        }
        return res;
    }
};

• Java

class Solution {
    public int romanToInt(String s) {

        HashMap<Character, Integer> hash = new HashMap<>();
        hash.put('I', 1); hash.put('V', 5);
        hash.put('X', 10); hash.put('L', 50);
        hash.put('C', 100); hash.put('D', 500);
        hash.put('M', 1000);

        char[] cs = s.toCharArray();

        int res = 0;
        for (int i = 0; i < cs.length; i++) {
            if (i + 1 < cs.length && hash.get(cs[i]) < hash.get(cs[i + 1])) res -= hash.get(cs[i]);
            else res += hash.get(cs[i]);
        }
        return res;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为s长度。

• 空间复杂度：$O(1)$。