问题
1 | Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. |
翻译:
罗马数字由七种不同的符号表示: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。4写成了4，因为1在5之前，所以减4。同样的原理也适用于数字9，也就是9。减法有六种应用:
- I可以把V(5)和X(10)放在前面，得到4和9。
- X可以放在L(50)和C(100)之前，得到40和90。
- C可以放在D(500)和M(1000)之前，得到400和900。
给定一个罗马数字，把它转换成整数。输入保证在1到3999之间。
示例1:
输入:“III”
输出:3
示例2:
输入:“IV”
输出:4
示例3:
输入:“IX”
输出:9
示例4:
输入:“LVIII”
输出:58
说明:L = 50, V= 5, III = 3。
例5:
输入:“MCMXCIV”
输出:1994
说明:M = 1000, CM = 900, XC = 90, IV = 4。
解题思路
罗马数字的定义：维基百科
在维基百科中，有条对我们本题解题很有帮助的一个规律，为：右加左减
在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
所以本题的思路就很清楚，我们从不遵从特性到遵从特性的情况逐步分析，可以分为3个思路:
思路一：直接按照字面来解决，我们可以先把罗马数字的含义记录到map，方便我们获取，包括特殊情况：”IV”等这类,然后循环获取字符，如果是’I’,’X’,’C’我们就获取下一个字符，看看能否组合成特殊的情况，如果组合成功，则加上值，并下标移动，如果失败，加上本身的值。其他情况则加上本身的值就ok了。
思路二：该思路是对思路一的一种改进，我们知道特殊情况都是由前一个和当前这个组成（当然也可以是当前这个和后一个符号组合，相比是前后方便一点，因为思路一其实就是前后判断），所以我们主要记录前一个字符，和当前字符能否组合成特殊字符，如果能，减去前一字符两倍的值。最终都是加上当前的值。
思路三：该思路是使用了上文提到的规律，如果左边的数小于右边的数，那么操作减法，相反则是加法。所以我们只需要判断前后大小，按照对应的计算方式，就可以算出值。
解题方法
第一种解体方法，按照我们的思路来编辑，代码如下
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
31Map<String, Integer> map = new HashMap<>(16);
map.put("I", 1);
map.put("V", 5);
map.put("IV", 4);
map.put("IX", 9);
map.put("X", 10);
map.put("XL", 40);
map.put("L", 50);
map.put("XC", 90);
map.put("C", 100);
map.put("CD", 400);
map.put("D", 500);
map.put("CM", 900);
map.put("M", 1000);
int result = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
String temp = String.valueOf(c);
if ((c == 'I' || c == 'X' || c == 'C') && (i + 1) < s.length()) {
String m = String.valueOf(new char[]{c, s.charAt(i + 1)});
if (map.get(m) != null) {
temp = m;
i++;
}
}
result += map.get(temp);
}
return result;时间复杂度: 该方案用了循环，循环层数为一，所以记为n,所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)
空间复杂度: 该方案使用了map存储罗马数值和阿拉伯数值的基本关系，是额外空间，不算空间复杂度，所以空间复杂度是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
29Map<String, Integer> map = new HashMap<>(7);
map.put("I", 1);
map.put("V", 5);
map.put("IV", 4);
map.put("IX", 9);
map.put("X", 10);
map.put("XL", 40);
map.put("L", 50);
map.put("XC", 90);
map.put("C", 100);
map.put("CD", 400);
map.put("D", 500);
map.put("CM", 900);
map.put("M", 1000);
char last = s.charAt(0);
int result = map.get(String.valueOf(last));
for (int i = 1; i < s.length(); i++) {
char c = s.charAt(i);
String temp = String.valueOf(new char[]{last, c});
Integer integer = map.get(temp);
if (integer != null) {
result = result - 2 * map.get(String.valueOf(last));
}
result += map.get(String.valueOf(c));
last = c;
}
return result;时间复杂度: 该方案用了循环，循环层数为一，所以记为n,所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)
空间复杂度: 该方案使用了map存储罗马数值和阿拉伯数值的基本关系，是额外空间，不算空间复杂度，所以空间复杂度是O(1);
第三种解题方法，代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22Map<Character, Integer> map = new HashMap<>(7);
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);
char last = s.charAt(0);
int result = map.get(last);
for (int i = 1; i < s.length(); i++) {
char c = s.charAt(i);
if (map.get(last) < map.get(c)) {
result = result - 2 * map.get(last);
}
result += map.get(c);
last = c;
}
return result;时间复杂度: 该方案用了循环，循环层数为一，所以记为n,所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)
空间复杂度: 该方案使用了map存储罗马数值和阿拉伯数值的基本关系，是额外空间，不算空间复杂度，所以空间复杂度是O(1);
总结
本题的大致解法如上所诉，方案1和2因为要存储多余字符，所以只能用字符串类型存储，这就导致了后续字符都要转成字符串，出现了额外的开销，这个还是比较痛苦的，相对方案3就直接存储了字符，直接取就ok了。