实现字符串转换规则

13.题目链接-来源:力扣(LeetCode)(简单)

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: “III”
输出: 3

思路:

这题其实可以做得比上一题巧妙,不懂为什么上题中等这题却是简单。首先转换思路比较直白,读入字符串,数值相应增加,那么跟前一题一样,需要先用个表之类的东西存储一下对应关系。难点在于,4和9的数码对应的字符串含有减法(如IX是 10 - 1 = 9,即后面的大数减去前面的小数)。
注意到,减法只会出现在大数前的小数,也就是减法永远出现在数字5,10前面的数字1处。而罗马字符整体上是从大到小显示的,一旦出现『小大』组合,便是小数变号。那么我们将字符串倒过来看,是不是就意味着,整体上是从小到大排列,一旦有『大小』组合,便是小数变号。只要此时在大数出现的时候,作一个负号标记,那么该大数往后的小数就一定需要加负号。(如MCMXCIV,倒序是VICXMCM,V是5,那么之后的I(1)就是负数,C是100,那么之后的X(10)就是负数,依此类推)
当然字符串逆序需要多一点点额外的开销,整体上原理跟官方题解没什么区别。
时间复杂度:O(1)
空间复杂度: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
32
33
34
35
36
37
38
39
40
class Solution {
public int romanToInt(String s) {
StringBuilder sb = new StringBuilder(s);

sb.reverse();
String sv = sb.toString();

int n = s.length();

boolean minusI = false, minusX = false, minusC = false;

int ans = 0;

for (int i = 0; i < n; i++) {
char c = sv.charAt(i);
switch(c) {
case 'I': ans += minusI ? -1 : 1;
break;
case 'V': ans += 5;
minusI = true;
break;
case 'X': ans += minusX ? -10 : 10;
minusI = true;
break;
case 'L': ans += 50;
minusX = true;
break;
case 'C': ans += minusC ? -100 : 100;
minusX = true;
break;
case 'D': ans += 500;
minusC = true;
break;
case 'M': ans += 1000;
minusC = true;
}
}
return ans;
}
}