Roman to Integer

13. Roman to Integer

分析


1	2	3	4	5	6	7	8	9
I	II	III	IV	V	VI	VII	VIII	IX
10	20	30	40	50	60	70	80	90
X	XX	XXX	XL	L	LX	LXX	LXXX	XL
100	200	300	400	500	600	700	800	900
C	CC	CCC	CD	D	DC	DCC	DCCC	CM
1000	2000	3000
M	MM	MMM

罗马数字采用加法规则，但某些情况下需要减法规则，例如：

加法规则：VI = 5 + 1 = 6，LXX = 50 + 10 + 10 = 70
减法规则：IV = 5 - 1 = 4，IX = 10 - 1 = 9

映射数值：
- 使用哈希表将罗马字符与对应数值建立映射关系，便于快速查找
遍历字符串：
- 加法逻辑：如果当前字符的数值大于等于后一个字符的数值，直接将当前字符的数值加到结果中
- 减法逻辑：如果当前字符的数值小于后一个字符的数值，则根据减法规则，将当前字符的数值从结果中减去。
边界处理：
- 遍历时检查 i + 1 是否越界，确保安全访问下一个字符
返回结果：
- 遍历完成后，累加结果即为罗马数字对应的整数

时间复杂度：

遍历字符串一次，查找哈希表的时间复杂度为 O(1)，因此整体为 O(n)，其中 n 是字符串的长度

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution
{
public:
    int romanToInt(string s)
    {
        // 哈希表：罗马字符到数值的映射
        std::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;  // 返回结果
    }
};