Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
这个题目首先要了解罗马数字的拼写规则(以下引自维基百科):
罗马数字共有7个,即I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)。按照下述的规则可以表示任意正整数。需要注意的是罗马数字中没有“0”,与进位制无关。一般认为罗马数字只用来记数,而不作演算。
C++代码实现如下:
int romanToInt(string s) {
unordered_map<char, int> basics;
basics[‘I‘] = 1;
basics[‘V‘] = 5;
basics[‘X‘] = 10;
basics[‘L‘] = 50;
basics[‘C‘] = 100;
basics[‘D‘] = 500;
basics[‘M‘] = 1000;
int result = 0;
int last = 0;
for (int i = s.size() - 1; i >= 0; --i) {
auto c = s[i];
if (basics[c] >= last) result += basics[c];
else result -= basics[c];
last = basics[c];
}
return result;
}
时间性能如下图所示:
Discuss上的这个解法可能更好理解:
public static int romanToInt(String s) {
int res = 0;
for (int i = s.length() - 1; i >= 0; i--) {
char c = s.[i];
switch (c) {
case ‘I‘:
res += (res >= 5 ? -1 : 1);
break;
case ‘V‘:
res += 5;
break;
case ‘X‘:
res += 10 * (res >= 50 ? -1 : 1);
break;
case ‘L‘:
res += 50;
break;
case ‘C‘:
res += 100 * (res >= 500 ? -1 : 1);
break;
case ‘D‘:
res += 500;
break;
case ‘M‘:
res += 1000;
break;
}
}
return res;
}
其时间性能如下图所示:
LeetCode[Math]: Roman to Integer
原文:http://blog.csdn.net/chfe007/article/details/44037079