LeetCode：Roman to Integer(罗马数字转整数) | Jacky's Blog

LeetCode：Roman to Integer(罗马数字转整数)

问题描述

copy自LeetCode：

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.

解决方法

问题大意是输入一个罗马数字字符串，输出一个10进制阿拉伯数字。
这个问题的难点在于如何确定需要做减法的组合，笔者的思路是将做减法的组合也放入和整数的映射关系表中，穷举所有的罗马数字组合，如下：

Symbol       Value
I             1
IV            4
V             5
IX            9
X             10
XL            40
L             50
XC            90
C             100
CD            400
D             500
CM            900
M             1000

那接下来就变成字符串分词的问题了，上表就是我们的字典，由于一个词长度最大为2，最小为1，所以我们每次读取两个罗马数字，然后到字典中去匹配，如果匹配不到，我们就要把这个长度为2的词拆开，分别再去字典中匹配。最后将翻译的整数相加就是结果，笔者用swift实现如下

func romanToInt(_ s: String) -> Int {
    let romanInfo:[String: Int] = ["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]

    let strList = Array(s) // 将字符串切割成数组
    
    var result = 0 // 结果
    var current = 0 // 游标
    
    while current < strList.count { // 结束条件
        // 当前需要处理的罗马数字
        let numChar = strList[current]
        
        // 获取相邻的下一个罗马数字
        var nextNumChar = ""
        if current + 1 < strList.count  {
            nextNumChar = String(strList[current + 1])
        }
        
        // 将两个字符组成一个词
        let numKey = "\(numChar)\(nextNumChar)"
        
        // 判断是否在字典中能匹配到
        if let num = romanInfo[numKey] {
            // 结果相加
            result += num
            
            // 移动游标
            current += 2
        } else {
            // 将组合的词拆开，只匹配该词中第一个罗马数字，（为什么只匹配第一个？因为第二个有可能和其相邻的下一个组合成一个字典中的词）
            if let num = romanInfo[String(numChar)] {
                // 结果相加
                result += num
            }
            
            // 移动游标
            current += 1
        }
    }
    
    return result
}

上述代码的执行在LeetCode的测试结果：
Runtime: 36 ms
Memory Usage: 20.7 MB
耗时打败了90.13%的swift提交

笔者还有个直接切割字符串的版本，解决思路没变，但是性能不佳(耗时60ms)，看来平时尽量减少字符串的频繁操作，转换成数组会好些，代码也贴出来了：

func romanToInt(_ s: String) -> Int {
    let romanInfo:[String: Int] = ["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]
    
    var result: Int = 0
    var current: Int = 0
    
    while current < s.count {
        let range = s.index(s.startIndex, offsetBy: current)..<s.index(s.startIndex, offsetBy: min(current+2, s.count))
        let subString = String(s[range])
        
        print("subString\(subString)")
        
        if let num = romanInfo[subString] {
            result += num
            current += 2
        } else {
            if let num = romanInfo[String(subString.prefix(1))] {
                result += num
            }
            current += 1
        }
    }
    
    return result
}