13. Roman to Integer

哎 题都懒得复制粘贴了，还要改格式好麻烦的。就是简单的把罗马计数方法改成现在普通的，比如X改成10；

思路1：正序

从头扫描到倒数第二个，拿每个数与后面的数比较，小就减这个数，否则就加这个数，最后加上最后一位

int romanToInt(string s) {
	map<char, int> m;
	m.insert(pair<char,int>('I',1));
	m.insert(pair<char, int>('V', 5));
	m.insert(pair<char, int>('X', 10));
	m.insert(pair<char, int>('L', 50));
	m.insert(pair<char, int>('C', 100));
	m.insert(pair<char, int>('D', 500));
	m.insert(pair<char, int>('M', 1000));

	int sz = s.size(), res = 0;
	for (int i = 0; i < sz - 1; ++i) {
		if (m[s[i]] < m[s[i + 1]]) 
			res -=  m[s[i]];
		else
			res += m[s[i]];
	}
	res += m[s[sz-1]];
	return res;
}

方法2：倒序

观察可得到规律，从罗马数末端开始计算，若出现低于之前出现最大值的数则计算为负数。

int romanToInt(string s) {
	map<char, int> m;
	m.insert(pair<char, int>('I', 1));
	m.insert(pair<char, int>('V', 5));
	m.insert(pair<char, int>('X', 10));
	m.insert(pair<char, int>('L', 50));
	m.insert(pair<char, int>('C', 100));
	m.insert(pair<char, int>('D', 500));
	m.insert(pair<char, int>('M', 1000));

	int sz = s.size(), res = 0;
	char max = 'I';
	for (int i = sz-1; i >=0; --i) {
		if (m[s[i]] < m[max])
			res -= m[s[i]];
		else {
			max = s[i];
			res += m[max];	
		}		
	}
	res += m[s[sz - 1]];
	return res;
}