1, 题目

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

  1. 字符          数值
  2. I             1
  3. V             5
  4. X             10
  5. L             50
  6. C             100
  7. D             500
  8. M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况.

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:

  1. 输入: "III"
  2. 输出: 3

示例 2:

  1. 输入: "IV"
  2. 输出: 4

示例 3:

  1. 输入: "IX"
  2. 输出: 9

示例 4:

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

1, 类似哈夫曼编码

第一步, 建立映射
第二步, 一个字母,两个字母开头key
第三步, 求和

#scala实现
object Solution {
    def romanToInt(s: String): Int = {
        val map = Map(
            "I" -> 1,
            "V" -> 5,
            "X" -> 10,
            "L" -> 50,
            "C" -> 100,
            "D" -> 500,
            "M" -> 1000,
            "IV" -> 4,
            "IX" -> 9,
            "XL" -> 40,
            "XC" -> 90,
            "CD" -> 400,
            "CM" -> 900
        )
        val one_char = List("V", "L", "D", "M")
        val two_char = List("IV", "IX", "XL", "XC", "CD", "CM")
        var sum = 0
        var i = 0
        while (i < s.length) {
            if (one_char.contains(s(i).toString)) {
                sum += map(s(i).toString)
            } else if (i <= s.length - 2 && two_char.contains(s.substring(i, i + 2))) {
                sum += map(s.substring(i, i + 2))
                i += 1
            } else {
                sum += map(s(i).toString)
            }
            i += 1
        }
        sum
    }
}

#python实现
class Solution:
    def romanToInt(self, s: str) -> int:
        roman = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000,
            'IV': 4,
            'IX': 9,
            'XL': 40,
            'XC': 90,
            'CD': 400,
            'CM': 900
        }
        one_char = ['V', 'L', 'D', 'M']
        two_char = ['IV', 'IX', 'XL', 'XC', 'CD', 'CM']
        sum = 0
        i = 0
        while i < len(s):
            if s[i] in one_char:
                sum += roman[s[i]]
            elif s[i:i + 2] in two_char:
                sum += roman[s[i:i + 2]]
                i += 1
            else:
                sum += roman[s[i]]
            i += 1
        return sum