当前位置：首页 > news >正文

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

news 2024/11/2 7:23:04

题目描述

罗马数字包含以下七种字符: 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) 时间内查询每个字符的数值。
遍历字符串：我们逐个遍历字符串的每一个字符。对于每个字符：
- 如果当前字符的数值比下一个字符小，则减去该字符的数值。
- 否则，将该字符的数值加到最终结果中。
返回结果：循环结束后，得到的结果就是转换后的整数。