算法研究-罗马数字转阿拉伯数字

这个系列是笔者练习LeetCode上的算法题的记录&分享

题目

罗马数字转整数（Roman to int）

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

字符|数值
-|-|-
I | 1
V | 5
X | 10
L | 50
C | 100
D | 500
M | 1000

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

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

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

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

• 示例 1:
  输入: “III”
  输出: 3

• 示例 2:
  输入: “IV”
  输出: 4

• 示例 3:
  输入: “IX”
  输出: 9

• 示例 4:
  输入: “LVIII”
  输出: 58
  解释: L = 50, V= 5, III = 3.

• 示例 5:
  输入: “MCMXCIV”
  输出: 1994
  解释: M = 1000, CM = 900, XC = 90, IV = 4.

Q:关于更大的罗马数字的显示方式，会专门写一个~

题解

需要注意的问题

1. 将罗马字符转为阿拉伯数字的规则

2. 罗马数字的特殊规则，小数在大数左边，则表示大数减去小数

3. 范围的限制问题

   其中第一个问题比较好解决，通过switch或者哈希表都可以解决。

   第二个问题，可以罗列出所有特殊例子（IV、IX、XL、XC、CD、CM）,可以通过匹配这六种特殊的例子得到数值。也可以通过特殊的规则来实现，通过比较左侧数是否小于右侧数。

   第三个问题，在最后返回的时候，做一个数值范围限制。

   代码

   版本一

   public class Solution {
   
       public int RomanToInt(string s)
       {
           int num = FindRoman(s[0]);
           char befor, now;
   
           for (int i = 1; i < s.Length; i++)
           {
               befor = s[i-1];
               now = s[i];
   
               if (FindRoman(befor) >= FindRoman(now))
               {
                   num += FindRoman(now);
               }
               else {
                   num += (FindRoman(now)- 2 * FindRoman(befor));
               }
           }
           if (num < 1) num = 0;
           if (num > 3999) num = 3999;
           return num;
       }
   
       int FindRoman(char roman) {
           switch (roman) {
               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;
           }
       }
   }

   通过，switch来匹配罗马字符表，并且通过判断左侧数值是否大于右侧数值来实现特殊规则。

   第一次提交，执行用时124ms，内存消耗24.5MB

版本二

public class Solution {
    public int RomanToInt(string s)
    {
        Hashtable findRoman = new Hashtable();
        findRoman.Add( 'I',1);
        findRoman.Add( 'V',5);
        findRoman.Add( 'X',10);
        findRoman.Add( 'L', 50);
        findRoman.Add( 'C', 100);
        findRoman.Add( 'D', 500);
        findRoman.Add( 'M', 1000);

        int num = findRoman[s[0]].GetHashCode();
        char befor, now;

        for (int i = 1; i < s.Length; i++)
        {
            befor = s[i-1];
            now = s[i];
            if (findRoman[befor].GetHashCode() >= findRoman[now].GetHashCode())
            {
                num += findRoman[now].GetHashCode();
            }
            else {
                num += (findRoman[now].GetHashCode() - 2 * findRoman[befor].GetHashCode());
            }
        }
        if (num < 1) num = 0;
        if (num > 3999) num = 3999;
        return num;
    }
}

代码行数减少，并且利用了哈希表来做罗马字符表的转换。

第一次执行：120ms，24.8MB

减少了时间，但是稍微增大了内存使用

P.S. 通过多次测试，发现，LeetCode的测试结果的数据有一定概率性，同样的代码得到的执行时间和内存消耗不一样。