- 1. 题目描述
- 2. 解题思路
- 3. 代码实现
- 3.1 向后多看一位（switch）
- 3.2 记住前一位数（hashmap）
- 3.3 记住前一位数（switch）
- 3.4 替换输入字符串（switch）
- 3.5 对比
这道题目的第一个思路就是先把输入的字符串转换成字符数组，对字符数组进行遍历，利用switch进行对应的罗马字符判断，然后判断特殊情况的时候向后看多一位。这种方法简单直接，应该大部分都能想得出来。但是运行了一下发现，嗯…问题是能解决的，但是效率不够高。
经过一番思考发现，每一次判断特殊情况都需要向后看多一位，影响效率，转变一下方式，我们可以每读一个字符就记下来，每次判断时利用上一次记下来的值进行比较，那就可以省去向后看多一位这个动作，一定程度上其实是属于空间换时间的操作（多存一个变量，少查一次），这种方法可以通过switch或hashmap实现。
做完以上两种尝试过后结果还不错，看了一眼题解能有什么奇招，发现还可以进行字符串替换，即把特殊情况的字符串都替换成自定义字符，方便后续进行运算，这个方法有点意思，但在效率上会稍微逊色。
3. 代码实现 3.1 向后多看一位（switch）public int romanToInt(String s) {
char[] chars = s.toCharArray();
int sum = 0;
int length = chars.length;
for (int i = 0; i < length; i++) {
switch (chars[i]) {
case 'I':
try {
if (chars[i + 1] == 'V' || chars[i + 1] == 'X') {
sum = sum - 1;
} else {
sum = sum + 1;
}
} catch (Exception e) {
return sum + 1;
}
break;
case 'X':
try {
if (chars[i + 1] == 'L' || chars[i + 1] == 'C') {
sum = sum - 10;
} else {
sum = sum + 10;
}
} catch (Exception e) {
return sum + 10;
}
break;
case 'C':
try {
if (chars[i + 1] == 'D' || chars[i + 1] == 'M') {
sum = sum - 100;
} else {
sum = sum + 100;
}
} catch (Exception e) {
return sum + 100;
}
break;
case 'V':
sum = sum + 5;
break;
case 'L':
sum = sum + 50;
break;
case 'D':
sum = sum + 500;
break;
case 'M':
sum = sum + 1000;
break;
}
}
return sum;
}
3.2 记住前一位数（hashmap）
public int romanToInt(String s) {
int sum = 0;
char[] chars = s.toCharArray();
HashMap changeMap = new HashMap<>();
changeMap.put('I', 1);
changeMap.put('V', 5);
changeMap.put('X', 10);
changeMap.put('L', 50);
changeMap.put('C', 100);
changeMap.put('D', 500);
changeMap.put('M', 1000);
int old = 1001;
for (char aChar : chars) {
Integer integer = changeMap.get(aChar);
if (old < integer) {
sum -= 2 * old;
}
sum += integer;
old = integer;
}
return sum;
}
3.3 记住前一位数（switch）
public int romanToInt(String s) {
int sum = 0;
char[] chars = s.toCharArray();
int old = 1001;
int integer = 0;
for (char aChar : chars) {
switch (aChar) {
case 'I':
integer = 1;
break;
case 'X':
integer = 10;
break;
case 'C':
integer = 100;
break;
case 'V':
integer = 5;
break;
case 'L':
integer = 50;
break;
case 'D':
integer = 500;
break;
case 'M':
integer = 1000;
break;
}
if (old < integer) {
sum -= 2 * old;
}
sum += integer;
old = integer;
}
return sum;
}
我所尝试的四种算法当中这种算法是最优的结果：
public int romanToInt(String s) {
int sum = 0;
s = s.replace("IV", "a");
s = s.replace("IX", "b");
s = s.replace("XL", "c");
s = s.replace("XC", "d");
s = s.replace("CD", "e");
s = s.replace("CM", "f");
char[] chars = s.toCharArray();
for (char aChar : chars) {
switch (aChar) {
case 'I':
sum += 1;
break;
case 'X':
sum += 10;
break;
case 'C':
sum += 100;
break;
case 'V':
sum += 5;
break;
case 'L':
sum += 50;
break;
case 'D':
sum += 500;
break;
case 'M':
sum += 1000;
break;
case 'a':
sum += 4;
break;
case 'b':
sum += 9;
break;
case 'c':
sum += 40;
break;
case 'd':
sum += 90;
break;
case 'e':
sum += 400;
break;
case 'f':
sum += 900;
break;
}
}
return sum;
}
3.5 对比
显然，采用哈希表的代码看上去更加优雅，但需要占用额外的存储空间，并且比switch略慢一点。
