LeetCode[Math]: Roman to Integer

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

这个题目首先要了解罗马数字的拼写规则（以下引自维基百科）：

罗马数字共有7个，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。按照下述的规则可以表示任意正整数。需要注意的是罗马数字中没有“0”，与进位制无关。一般认为罗马数字只用来记数，而不作演算。

重复数次：一个罗马数字重复几次，就表示这个数的几倍。右加左减： 加线乘千： 在罗马数字的上方加上一条横线或者加上下标的，表示将这个数乘以1000，即是原数的1000倍。同理，如果上方有两条横线，，即是原数的1000000（1000^{2}）倍。数码限制： 同一数码最多只能出现三次，如40不可表示为XXXX，而要表示为XL。例外：由于IV是古罗马神话主神朱庇特（即IVPITER，古罗马字母里没有J和U）的首字，因此有时用IIII代替IV。

C++代码实现如下：

int romanToInt(string s) {unordered_map<char, int> basics;basics[‘I’] = 1;basics[‘V’] = 5;basics[‘X’] = 10;basics[‘L’] = 50;basics[‘C’] = 100;basics[‘D’] = 500;basics[‘M’] = 1000;int result = 0;int last = 0;for (int i = s.size() – 1; i >= 0; –i) {auto c = s[i];if (basics[c] >= last) result += basics[c];else result -= basics[c];last = basics[c];}return result;}

时间性能如下图所示：

Discuss上的这个解法可能更好理解：

(String s) {int res = 0;for (int i = s.length() – 1; i >= 0; i–) {char c = s.[i];switch (c) {case ‘I’:res += (res >= 5 ? -1 : 1);break;case ‘V’:res += 5;break;case ‘X’:res += 10 * (res >= 50 ? -1 : 1);break;case ‘L’:res += 50;break;case ‘C’:res += 100 * (res >= 500 ? -1 : 1);break;case ‘D’:res += 500;break;case ‘M’:res += 1000;break;}}return res;}

其时间性能如下图所示：

在泪水中浸泡过的微笑最灿烂，从迷惘中走出来的灵魂最清醒。