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 - 左边 + 右边。


代码如下：

intromanToInt(strings){if(s.size()==0)return0;stringleft,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));intmaxGrade=0;//最高级charmaxChar='\0';intmaxGrades=0;//最高级次数intmaxGradePos=0;//最高级位置for(inti=0;i<s.size();i++)//获取最高级字符，最高级位置{if(romanMap[s[i]]>maxGrade){maxGrade=romanMap[s[i]];maxChar=s[i];maxGradePos=i;}}for(inti=maxGradePos;i<s.size();i++)//获取最高级连续次数{if(s[i]==maxChar)maxGrades++;elsebreak;}left=s.substr(0,maxGradePos);right=s.substr(maxGradePos+maxGrades);returnmaxGrades*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结束。

代码如下：

classSolution{public:intromanToInt(strings){intsum=0;intstart=0;charchar_arr[]={'I','V','X','L','C','D','M'};intint_arr[]={1,5,10,50,100,500,1000};std::map<char,int>roman_map;intmap_len=sizeof(char_arr)/sizeof(char);for(inti=0;i<map_len;++i)roman_map.insert(std::pair<char,int>(char_arr[i],int_arr[i]));for(inti=0;i<s.length()-1;++i){if(roman_map[s[i]]>=roman_map[s[i+1]])sum+=roman_map[s[i]];elsesum-=roman_map[s[i]];}sum+=roman_map[s[s.length()-1]];returnsum;}};


2016-08-10 15:44:23