[LeetCode] 13. Roman to Integer

轉自LeetCode

Given a roman numeral, convert it to an integer.

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

<Solution>

這題和 Integer to Roman 剛好相反

這邊要運用到羅馬數字的一些特性 (參考資料)

Symbol	I	V	X	L	C	D	M
Value	1	5	10	50	100	500	1,000

Number	4	9	40	90	400	900
Notation	IV	IX	XL	XC	CD	CM

• I、X、C 這三個數字，連在一起用，或是放在比它大的數的右邊當加法用時，最多只能三個；放在比它大的數的左邊當減法用時，最多只能一個

    例如 : III = 3、IV = 4、XX = 20、LX = 60、LXXX = 80、XC = 90

    沒有 XXC = 80，這是不符合規則的

• V、L、D，這三個數不能放在比它大的數的左邊，拿來當減法用
• V 和 X 左邊只能放 I
• L 和 C 左邊只能放 X
• D 和 M 左邊只能放 C

因為題目會給符合規則的羅馬數字

所以綜合以上規則，可以得出以下想法

• 只判斷是不是 I、V、X、L、C、D、M
• 如果是最後一個字元，直接加上對應數值
• 如果不是最後一個字元，檢查下一個字元的對應數值，是不是比目前的大；是的話，代表目前的數值是用來當減法，要減掉、不是的話，就加上對應數值
• 非上述情況，就減掉

寫成 code 如下

	class Solution {
	public:
	int romanToInt(string s) {
	int ans = 0;
	unordered_map<char, int> table = {{'I',1}, {'V',5}, {'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
	for(int i = 0; i < s.length(); i++) {
	if(i == s.length() - 1 || table[s[i+1]] <= table[s[i]]) {
	ans += table[s[i]];
	}
	else {
	ans -= table[s[i]];
	}
	}
	return ans;
	}
	};

view raw romanToInt.cpp hosted with ❤ by GitHub