LeetCode | 3. Roman to Integer 罗马数字转整数

关注
发布于: 2020 年 06 月 08 日
Roman to Integer 是 LeetCode 算法题库中的第十三道题，难度为 Easy，题目地址为：https://leetcode.com/problems/roman-to-integer/
1. 问题描述给定一个罗马数字，将其转换成整数，输入确保在1 至 3999的范围内。
﻿
罗马数字是包含以下七种字符的一种数字表示方式：I, V, X, L, C, D, 和 M。通常情况下，罗马数字中小的数字在大的数字的右边，但也有特殊的情况，比如 I 在 V 和 X 左边，分别表示 4 和 9；X 在 L 和 C 左边来表示 40 和 90；C 在 D 和 M 的左边，来表示 400 和 900。
﻿
示例：
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
﻿
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
﻿
2. 解题思路该题有好几种解题思路，我一开始想到的是将字符串转字符，然后来判断该字符对应的数字，但是没想好怎么处理 IV 、IX 这类情况。参看其他人的讨论和解题思路后，最终选择了两种理解较为简单的方法，虽然在算法实现上效率可能不高。 
前后数字对比法，就是遍历所有的罗马数字，然后根据其对应的数值做加法。其中，需要把当前的数字与前一个数字进行比较，如果小于前一个数字，则正常的做加法；如果大于前一个数字，那么说明当前数字与前一个数字是一个特例组合，需要减去两倍的前一个数字。比如，IV，先是遍历第一个元素为 I，其值为 1，做加法，总和为 1；遍历到第二个元素为 V，正常的做加法，总和为 6。然后做判断，发现 V 要大于 I，那么就是特例了，需要减去两倍的前一个数字，最后的结果为 4。
正则表达式法，该方法是将所有的罗马数字的组合罗列出来，通过正则表达式来找到不同的组合，并求和。在正则表达式的模式识别上，需要注意罗马数字组合的顺序，比如 IV 一定要在I前面，否则正则表达式的判断都是优先提取出 I 来。
3. 知识点对于 Python 的实现，知识点包括：
对「字典」的使用和理解
对正则表达式的使用和理解
﻿
对于 C# 的实现，知识点在于：
如何直接从字符串中得到对应的字符
如何实现类似于 Python 字典的功能
如何使用正则表达式及其
4. 代码Python﻿
前后两数对比法：
class Solution:
    def romanToInt(self, s: str) -> int:
        roman_to_int = {
            “I”:1, “V”:5, “X”:10, “L”: 50 , “C”: 100, “D”: 500, “M”: 1000
        }
        
        total = 0
        prev_value = 0
        
        for letter in s:
            value = roman_to_int[letter]
            total += value
            
            if value > prev_value:
                total -= 2 * prev_value
            prev_value = value
        return total
﻿
正则表达式法：
重点在于正则表达式匹配模式的顺序：r’IV|IX|I|V|XL|XC|X|L|CD|CM|C|D|M’
class Solution:
    def romanToInt(self, s: str) -> int:
        roman_to_int = {
            “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
        }
        
        pattern_re = re.compile(r’IV|IX|I|V|XL|XC|X|L|CD|CM|C|D|M’)
        
        result = 0
        for m in re.finditer(pattern_re, s):
            result += roman_to_int[m.group(0)]
        
        return result
﻿
﻿
C#前后两数对比法：
这里是直接通过s[i]来得到字符串对应索引的字符，通过引入一个函数来实现类似于 Python 字典的快速匹配功能。
﻿
public class Solution {
    public int RomanToInt(string s) {
        int total = 0;
        int prev_result = 0;
        for (int i = 0; i < s.Length; i++)
        {
            int current_result = get_value(s[i]);
            total += current_result;
            
            if (current_result > prev_result)
            {
                total -= 2 * prev_result;
            }
            prev_result = current_result;
        }
        
        return total;
    }
    
    private int get_value(char ch)
    {
        switch(ch)
        {
            case ‘I’: return 1;
            case ‘V’: return 5;
            case ‘X’: return 10;
            case ‘L’: return 50;
            case ‘C’: return 100;
            case ‘D’: return 500;
            case ‘M’: return 1000;
            default: return 0;
        }
    }
}
﻿
正则表达式法：
这里是直接参考来官网关于正则表达式介绍的代码片段。
﻿
using System.Text.RegularExpressions;
public class Solution {
    public int RomanToInt(string s) {
        int total = 0;
        
        string pattern = @“IV|IX|I|V|XL|XC|X|L|CD|CM|C|D|M”;
        Regex rx = new Regex(pattern);
        MatchCollection matches = rx.Matches(s);
        
        foreach (Match match in matches)
        {
            GroupCollection groups = match.Groups;
            total += get_value(groups[0].Value);
        }
        
        return total;
    }
    
    private int get_value(string str)
    {
        switch(str)
        {
            case “I”: return 1;
            case “IV”: return 4;
            case “V”: return 5;
            case “IX”: return 9;
            case “X”: return 10;
            case “XL”: return 40;
            case “L”: return 50;
            case “XC”: return 90;
            case “C”: return 100;
            case “CD”: return 400;
            case “D”: return 500;
            case “CM”: return 900;
            case “M”: return 1000;
            default: return 0;
        }
    }
}
﻿
﻿
发布于: 2020 年 06 月 08 日阅读数: 57
原文链接:【http://xie.infoq.cn/article/b0173b850c6b9626974760cd7】。文章转载请联系作者。
Puran

关注
GIS从业者，正在往开发的路上小跑。 2018.03.29 加入
从业4年的GIS开发小白，work@esri。
发布
暂无评论
创作场景

LeetCode | 3. Roman to Integer 罗马数字转整数

1. 问题描述

2. 解题思路

3. 知识点

4. 代码

Python

C#

Puran

评论
