13. Roman to Integer

今天我们一起挑战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, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 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.

Example 1:
Input: s = "III"
Output: 3

Example 2:
Input: s = "IV"
Output: 4

Example 3:
Input: s = "IX"
Output: 9

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

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

这题是希望我们把罗马数字转换成阿拉伯数字，并告诉我们转换的规则，而规则中大部分是罗马数字与数字一一对应的，且阿拉伯数字原则上也需由大到小排，但其中有一些特列，譬如4就可以用IV来表示，9可以用IX来表示，90可以用XC来表示，依此类推。
题目会给我们一串字串，并要求回传一个整数。

HahsMap

按照题目的要求与特性我们可以发现，用一个HashMap可以快速达到把字符转换成数字，程序码易读性也会增加，因此我们可以事先建立HashMap来转换罗马数字与数字，接着走访字串，把走访到的字元利用HashMap转换成整数加进我们最後要回传的变数中

但在过程我们必须做检查，就是检查上面提到的特例，我们可以检查走访到的数字是否比下个数字大，如果是的话表示此时走访到例外，我们就不要加进变数中，反而要用减的，这样才会符合题目要求。

以下是python的程序码

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_dic = {
            'M': 1000, 
            'D': 500, 
            'C': 100, 
            'L': 50, 
            'X': 10, 
            'V': 5, 
            'I': 1
        }  # 建立杂凑表
        result = 0
        for i in range(len(s)-1):
            if roman_dic[s[i]] < roman_dic[s[i+1]]:  # 发现特例
                result -= roman_dic[s[i]]
            else:
                result += roman_dic[s[i]]
        result += roman_dic[s[-1]]  # 要记得走访完最後一个
        return result

以下是C++的程序码

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