leetCode 13. Roman to Integer 字符串

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。

思路：

1. 将字符串分为3部分，left，mid，right。

2. 获取当前字符串的最大单位m。记录位置，字符。

3. 获取最大单位连续出现的次数n。

4. 通过递归，结果为m*n - 左边 + 右边。

代码如下：

int romanToInt(string s) {        if (s.size() == 0)                return 0;        string left, right;        map romanMap;        romanMap.insert(pair('I', 1));        romanMap.insert(pair('V', 5));        romanMap.insert(pair('X', 10));        romanMap.insert(pair('L', 50));        romanMap.insert(pair('C', 100));        romanMap.insert(pair('D', 500));        romanMap.insert(pair('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结束。

代码如下：

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 roman_map;          int map_len = sizeof(char_arr)/sizeof(char);           for (int i = 0; i< map_len; ++i)               roman_map.insert(std::pair (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;      }};

2016-08-10 15:44:23