leetCode13.RomantoInteger字符串

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


文章名称:leetCode13.RomantoInteger字符串
文章来源:http://myzitong.com/article/gpgpjp.html