模拟
题目已经把罗马数字的规则给得很清楚了，普通情况就是把每个字符对应的数值累加，特殊情况则是六种固定的双字符组合，因此可以直接按照题意模拟转换过程。
遍历字符串时，优先判断当前位置和下一位置能否组成特殊组合，如果可以就加上对应数值并跳过下一位，否则按单个字符进行转换即可。
时间复杂度 $O(n)$
空间复杂度 $O(1)$
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
27
28
29
30
31
| class Solution {
private static final Map<String, Integer> map = new HashMap<>();
static {
map.put("IV", 4);
map.put("IX", 9);
map.put("XL", 40);
map.put("XC", 90);
map.put("CD", 400);
map.put("CM", 900);
}
public int romanToInt(String s) {
int n = s.length(), ans = 0;
for (int i = 0; i < n; ++i) {
if (i + 1 < n && map.containsKey(s.substring(i, i + 2))) {
ans += map.get(s.substring(i, i + 2));
i++;
} else {
switch (s.charAt(i)) {
case 'I' -> ans += 1;
case 'V' -> ans += 5;
case 'X' -> ans += 10;
case 'L' -> ans += 50;
case 'C' -> ans += 100;
case 'D' -> ans += 500;
case 'M' -> ans += 1000;
}
}
}
return ans;
}
}
|
也可以不专门判断六种特殊组合，而是从规则本身出发。
如果当前字符对应的数值小于右边字符，那么它在答案中应当被减去，例如 $IV$ 中的 $I$，$IX$ 中的 $I$，$CM$ 中的 $C$。反之，如果当前字符大于等于右边字符，那么它就正常加到答案中。
这样只需要一次遍历，就能把普通情况和特殊情况统一处理掉。
时间复杂度 $O(n)$
空间复杂度 $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
private static final Map<Character, Integer> map = new HashMap<>();
static {
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
}
public int romanToInt(String s) {
int n = s.length(), ans = 0;
for (int i = 0; i < n; ++i) {
int cur = map.get(s.charAt(i));
if (i + 1 < n && cur < map.get(s.charAt(i + 1))) {
ans -= cur;
} else {
ans += cur;
}
}
return ans;
}
}
|