leetCode13.RomantoInteger字符串

13. Roman to Integer

創(chuàng)新互聯(lián)服務項目包括東港網(wǎng)站建設、東港網(wǎng)站制作、東港網(wǎng)頁制作以及東港網(wǎng)絡營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關系等，向廣大中小型企業(yè)、政府機構等提供互聯(lián)網(wǎng)行業(yè)的解決方案，東港網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務的客戶以成都為中心已經(jīng)輻射到東港省份的部分城市，未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任！

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

補充：羅馬數(shù)字

羅馬數(shù)字共有七個，即I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)。按照下面的規(guī)則可以表示任意正整數(shù)。

重復數(shù)次：一個羅馬數(shù)字重復幾次，就表示這個數(shù)的幾倍。 

右加左減：在一個較大的羅馬數(shù)字的右邊記上一個較小的羅馬數(shù)字，表示大數(shù)字加小數(shù)字。在一個較大的數(shù)字的左邊記上一個較小的羅馬數(shù)字，表示大數(shù)字減小數(shù)字。但是，左減不能跨越等級。比如，99不可以用IC表示，用XCIX表示。 

加線乘千：在一個羅馬數(shù)字的上方加上一條橫線或者在右下方寫M，表示將這個數(shù)字乘以1000，即是原數(shù)的1000倍。同理，如果上方有兩條橫線，即是原數(shù)的1000000倍。 

單位限制：同樣單位只能出現(xiàn)3次，如40不能表示為XXXX，而要表示為XL。


思路：

  1. 將字符串分為3部分，left，mid，right。

  2. 獲取當前字符串的最大單位m。記錄位置，字符。

  3. 獲取最大單位連續(xù)出現(xiàn)的次數(shù)n。

  4. 通過遞歸，結果為m*n - 左邊 + 右邊。

代碼如下：

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;//最高級次數(shù)
	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++)//獲取最高級連續(xù)次數(shù)
	{
		if (s[i] == maxChar)
			maxGrades++;
		else
			break;
	}
	left = s.substr(0, maxGradePos);
	right = s.substr(maxGradePos + maxGrades);
	return maxGrades * maxGrade - romanToInt(left) + romanToInt(right);
}


參考他人做法：

參考網(wǎng)址：http://blog.csdn.net/feliciafay/article/details/17259547

觀察到羅馬數(shù)字和Integer的轉換的小規(guī)律是：

IV = 5 -  1 =  (-1) + 5 = 4

VI = 5 + 1 = 5 + 1 = 6

I在V前面，由于I比V小，所以I被解釋為負數(shù)。

V在I后面，由于V比I大，所以V給解釋為整數(shù)。

繼續(xù)看幾個例子。

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<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;  
    }
};

2016-08-10 15:44:23

網(wǎng)站欄目：leetCode13.RomantoInteger字符串
轉載來源：http://muchs.cn/article28/gpgpjp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供云服務器、手機網(wǎng)站建設、服務器托管、建站公司、網(wǎng)站建設、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站托管運營