C++实现LeetCode(13.罗马数字转化成整数)

[LeetCode] 13. Roman to Integer 罗马数字转化成整数

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X+ II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X(10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

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

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

罗马数转化成数字问题，我们需要对于罗马数字很熟悉才能完成转换。以下截自百度百科：

I - 1

V - 5

X - 10

L - 50

C - 100 

D - 500

M - 1000

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

我们也可以每次跟前面的数字比较，如果小于等于前面的数字，先加上当前的数字，比如 "VI"，第二个字母 'I' 小于第一个字母 'V'，所以要加1。如果大于的前面的数字，加上当前的数字减去二倍前面的数字，这样可以把在上一个循环多加数减掉，比如 "IX"，我们在 i=0 时，加上了第一个字母 'I' 的值，此时结果 res 为1。当 i=1 时，字母 'X' 大于前一个字母 'I'，这说明前面的1是要减去的，而由于前一步不但没减，还多加了个1，所以此时要减去2倍的1，就是减2，所以才能得到9，整个过程是 res = 1 + 10 - 2 = 9，参见代码如下:

解法二：

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