13. Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
补充：罗马数字
罗马数字共有七个，即I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)。按照下面的规则可以表示任意正整数。
重复数次：一个罗马数字重复几次，就表示这个数的几倍。
右加左减：在一个较大的罗马数字的右边记上一个较小的罗马数字，表示大数字加小数字。在一个较大的数字的左边记上一个较小的罗马数字，表示大数字减小数字。但是，左减不能跨越等级。比如，99不可以用IC表示，用XCIX表示。
加线乘千：在一个罗马数字的上方加上一条横线或者在右下方写M，表示将这个数字乘以1000，即是原数的1000倍。同理，如果上方有两条横线，即是原数的1000000倍。
单位限制：同样单位只能出现3次，如40不能表示为XXXX，而要表示为XL。
思路：
-
将字符串分为3部分，left，mid，right。
-
获取当前字符串的最大单位m。记录位置，字符。
-
获取最大单位连续出现的次数n。
-
通过递归，结果为m*n - 左边 + 右边。
代码如下：
|
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
|
int
romanToInt(string s) {
if
(s.size() == 0)
return
0;
string left, right;
map<
char
,
int
> romanMap;
romanMap.insert(pair<
char
,
int
>(
'I'
, 1));
romanMap.insert(pair<
char
,
int
>(
'V'
, 5));
romanMap.insert(pair<
char
,
int
>(
'X'
, 10));
romanMap.insert(pair<
char
,
int
>(
'L'
, 50));
romanMap.insert(pair<
char
,
int
>(
'C'
, 100));
romanMap.insert(pair<
char
,
int
>(
'D'
, 500));
romanMap.insert(pair<
char
,
int
>(
'M'
, 1000));
int
maxGrade = 0;
//最高级
char
maxChar =
'\0'
;
int
maxGrades = 0;
//最高级次数
int
maxGradePos = 0;
//最高级位置
for
(
int
i = 0; i < s.size(); i++)
//获取最高级字符，最高级位置
{
if
(romanMap[s[i]] > maxGrade)
{
maxGrade = romanMap[s[i]];
maxChar = s[i];
maxGradePos = i;
}
}
for
(
int
i = maxGradePos; i < s.size(); i++)
//获取最高级连续次数
{
if
(s[i] == maxChar)
maxGrades++;
else
break
;
}
left = s.substr(0, maxGradePos);
right = s.substr(maxGradePos + maxGrades);
return
maxGrades * maxGrade - romanToInt(left) + romanToInt(right);
}
|
参考他人做法：
参考网址：http://blog.csdn.net/feliciafay/article/details/17259547
观察到罗马数字和Integer的转换的小规律是：
IV = 5 - 1 = (-1) + 5 = 4
VI = 5 + 1 = 5 + 1 = 6
I在V前面，由于I比V小，所以I被解释为负数。
V在I后面，由于V比I大，所以V给解释为整数。
继续看几个例子。
VII = 5 + 1 + 1 = 7
IX = (-1) + 10 = 9
所以，可以一次把输入字符串扫描一遍，从第一个字符开始，到最后一个字符为止，一次比较当前字符a和当前字符的下一个字符b。如果a< b ，解释为 b - a,否则如果a >= b， 解释为a + b。 实际上，由于每次总是比较2个相邻的字符，所以是下标是从0开始，到inputstring.length()-2结束。
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class
Solution {
public
:
int
romanToInt(string s) {
int
sum = 0;
int
start = 0;
char
char_arr[] = {
'I'
,
'V'
,
'X'
,
'L'
,
'C'
,
'D'
,
'M'
};
int
int_arr[] = {1, 5, 10, 50, 100, 500, 1000};
std::map<
char
,
int
> roman_map;
int
map_len =
sizeof
(char_arr)/
sizeof
(
char
);
for
(
int
i = 0; i< map_len; ++i)
roman_map.insert(std::pair<
char
,
int
> (char_arr[i], int_arr[i]));
for
(
int
i = 0; i < s.length() - 1; ++i) {
if
(roman_map[s[i]]>=roman_map[s[i + 1]])
sum += roman_map[s[i]];
else
sum -= roman_map[s[i]];
}
sum += roman_map[s[s.length()-1]];
return
sum;
}
};
|
