力扣(LeetCode)13. 罗马数字转整数(C++)

模拟

罗马数字和掰手指数数的区别在于，$IV/IX$ 这类倒着数数的，和阿拉伯数字最大的区别在于 $5$ 的 $10^k$ 倍 $k\in N$ ，需要被表示出来。所以除了记录 $I/X/C/M$ ——$1/10/100/1000$，还要记录 $V/L/D$——$5/50/500$ 。 倒着数数的数字，其实是减去第一个数，加上第二个数。考虑 $IV=-I+V=-1+5=4$ 。

代码展示

class Solution {
public:
    int romanToInt(string s) {
        unordered_map <char,int> mp{
            {'I',1},
            {'V',5},
            {'X',10},
            {'L',50},
            {'C',100},
            {'D',500},
            {'M',1000}
        };
        int ans = 0;
        for(int i = 0;i<s.size();i++){
            if(i<s.size()-1&&mp[s[i]]<mp[s[i+1]]) ans-=mp[s[i]];
            else ans+=mp[s[i]];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度 $O(n)$ ， $n$ 是 $s$ 的长度，加或减每一位所有罗马数字的时间复杂度 $O(n)$。

空间复杂度 $O(|C|)$ ， 编码使用哈希表的空间复杂度 $O(|C|)$ ， $|C|=7$ 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC