【每日一题】LeetCode - 罗马数字转整数

题目描述

罗马数字包含以下七种字符: I, V, X, L, C, D 和 M。每个字符对应的数值如下：

字符	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

例如：

罗马数字 2 写作 II，即两个 1 的并列。
数字 12 写作 XII，即 X + II。
数字 27 写作 XXVII，即 XX + V + II。

特殊规则

在罗马数字中，小的数字通常写在大的数字右边，但是有一些例外情况：

4 不写作 IIII，而是写作 IV。这是因为 I 在 V 左边，表示 5 - 1 = 4。
9 表示为 IX，表示 10 - 1 = 9。
其他的特例还包括：
- X 可以放在 L (50) 和 C (100) 左边表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 左边表示 400 和 900。

思路分析

转换罗马数字到整数的思路主要遵循以下步骤：

根据字符和数值的映射关系，把每个字符对应的数值取出来。
从左到右遍历罗马数字字符串：
- 如果某个字符对应的数值小于下一个字符的数值，说明需要用减法（如 IV 表示 4）。
- 否则，就把当前字符对应的数值加到结果中。

代码实现

如果你不知道unordered_map的用法可以看我另外一篇文章

【编程语言】在C++中使用map与unordered_map

#include "bits/stdc++.h"

using namespace std;

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> map = {
            {'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++) {
            int n = map[s[i]];
            if (i + 1 < s.size() && map[s[i + 1]] > n) {
                ans -= n;
            } else {
                ans += n;
            }
        }
        return ans;
    }
};

int main() { 
    Solution s;
    cout << s.romanToInt("III") << endl;
    return 0; 
}

代码讲解

字符映射：我们用 unordered_map 来映射每个罗马字符到对应的数值。这样可以在 O(1) 时间内查询每个字符的数值。
遍历字符串：我们逐个遍历字符串的每一个字符。对于每个字符：
- 如果当前字符的数值比下一个字符小，则减去该字符的数值。
- 否则，将该字符的数值加到最终结果中。
返回结果：循环结束后，得到的结果就是转换后的整数。