leetcodde 13.罗马数字转整数

leetcodde 13.罗马数字转整数

题目描述

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

示例 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.

题解一

先从一个简单的入手,我们来看看数字 I 和数字V,他们两的组合在一起会有两种结果:
IV 表示4,即左边的I1,右边的V5,右边数字减去左边数字也就是5-1得到4
VI 表示6,即左边的V5,右边的I1,左边数字加上右边数字,也就是5+1得到6
也就是小的数字在左边就是两数字相减,小的数字在右边就是两数相加。
我们不妨把不同字母的两两组合都列出来观察一下,按照题目的意思,两两组合其实有很多限制,像IM就不是一个合法的组合,小数字在左边的只有6种情况,我们把这六种情况都列出来,同时再列出小数字在右边的情况,然后对比一下。

通过这个图你就可以发现,这其实就是一个加减的问题。

那么对于这题,我们有两种实现方式
第一种方式,每次只匹配一个然后不断累加,如果前一个字母的值小于后一个字母的值,这次就不是累加了,而是做一个减法,也就是将当前字母的减掉,比如CM,我们先减去100,再加上1000这样就得到了900。详细执行过程见下图:

第二种,我们可以给每个字母,以及6种不同的两两组合都建一个哈希映射, 也就是将I IV V IX X XL L XC C CD D CM M 这些字母都放到哈希表中,如I=5IV=4,这样。具体执行过程如下图所示:

然后每次遍历的时候尽可能多的匹配,先匹配2个,如果两个不行就匹配1。像上面那个罗马数字中,MC就找不到对应的匹配,于是就只匹配一个M,第二次发现CM在哈希表中,于是一次匹配了两个。

java代码:

class Solution {
    public int romanToInt(String s) {
        if(s==null) {
            return 0;
        }
        //建立罗马数字 到 阿拉伯数字的映射关系
        Map<Character,Integer> str2int = new HashMap<Character,Integer>();
        str2int.put('I',1);
        str2int.put('V',5);
        str2int.put('X',10);
        str2int.put('L',50);
        str2int.put('C',100);
        str2int.put('D',500);
        str2int.put('M',1000);
        int ans = 0;
        //每次我们都匹配一个字母,注意因为要获取 i+1 位置的字母,所以循环终止条件
        //是字符串的最大长度-1
        for(int i=0;i<s.length()-1;++i) {
            if( str2int.get(s.charAt(i)) < str2int.get(s.charAt(i+1)) ) {
                ans -= str2int.get(s.charAt(i));
            }
            else {
                ans += str2int.get(s.charAt(i));
            }
        }
        //最后不要忘记收尾操作,把遗留的字母也加上
        ans += str2int.get(s.charAt(s.length()-1));
        return ans;
    }
}	
                                                                                         

python代码:

class Solution(object):
    def romanToInt(self, s):
        if not s:
            return 0
        # 建立罗马数字 到 阿拉伯数字的映射关系
        d = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}		
        ans = 0
        n = len(s)
        # 每次我们都匹配一个字母,注意因为要获取 i+1 位置的字母,所以循环终止条件
        # 是字符串的最大长度-1
        for i in xrange(n-1):
            if d[s[i+1]]>d[s[i]]:
                ans -= d[s[i]]
            else:
                ans += d[s[i]]
        # 最后不要忘记收尾操作,把遗留的字母也加上
        ans += d[s[n-1]]
        return ans
                                                                                     

题解二

题解一中根据罗马数字获取对应的整数是这么做的(以java为例)

str2int.get(s.charAt(i))

这里是获取字符串中第i个位置上的字符,返回的是char类型,因为java的Map键值对都必须是对象类型,所以char类型会被自动包装成对象类型,去map中查找对应的值。
值的类型是Integer,也是对象类型,之后Integer对象中的值会被自动转换成整型也就是int,这一切都是虚拟机帮我们做的,我们无需关心。

这就是相当于来回倒腾,当然虚拟机可以在运行期间自动优化,提高一些性能,但也免不了来回倒腾。
另外语言本身提供的哈希表虽然很强大,但是我们这里要的其实很简单,就是给出几个字符,然后能返回出对应的数字就行了,语言本身提供的哈希表显得有点了。

现在我们换一个思路,不再用语言提供的哈希表,我们自己实现一个,以此来加速查找过程。

首先我们得想想怎么根据一个字母获取到对应的整数,我们可以用字母本身做文章,每个字母在实际存储的时,存的是对应的ASCII码

上图中罗马数字相关的几个字母都被我标记出来了,比如I的ASCII码是73,我们拿到I也就知道实际存储的是73这个十进制值。

之后我们用自己实现的哈希函数来将73映射成1

上图就是一个哈希映射规则,I是73,经过(73-67)&0xF结果是6,于是就去索引下标6的位置去查找,得到的值是1
这样就建立了I -> 1的映射关系。
其他几个字母也是类似的。

但是,罗马数字只有7个,这里的数组大小为什么是11。
这是因为防止哈希冲突导致的,7个字母最理想情况是映射到长度为7的数组中,字母和数字一一对应。
但是这很难,比如下面这样的哈希函数就会冲突了,因为数组太小了,就容易出现冲突。

最终我们用上面的哈希函数,以及大小为10的整数数组,替换掉原先的哈希表,就完成了自定义的映射规则,代码实现跟解法一是一样的,只是映射规则变了。

java代码:

class Solution {
    public int romanToInt(String s) {
        if(s==null) {
            return 0;
        }
        int[] str2int = {100,500,0,5,0,10,1,0,0,50,1000};
        int ans = 0;
        for(int i=0;i<s.length()-1;++i) {
            //自定义的哈希映射规则,其他操作跟题解一中的代码都一样
            if( str2int[(s.charAt(i)-67)&0xF] < str2int[(s.charAt(i+1)-67)&0xF] ) {
                ans -= str2int[(s.charAt(i)-67)&0xF];
            }
            else {
                ans += str2int[(s.charAt(i)-67)&0xF];
            }
        }
        ans += str2int[(s.charAt(s.length()-1)-67)&0xF];
        return ans;
    }
}	
                                                                                           

python代码

class Solution(object):
    def romanToInt(self, s):
        if not s:
            return 0
        d = (100,500,0,5,0,10, 1, 0, 0,50,1000)
        ans = 0
        n = len(s)
        for i in xrange(n-1):
            # 自定义的哈希映射规则,其他操作跟题解一中的代码都一样
            if d[(ord(s[i+1])-67)&0xF] > d[(ord(s[i])-67)&0xF]:
                ans -= d[(ord(s[i])-67)&0xF]
            else:
                ans += d[(ord(s[i])-67)&0xF]
        ans += d[(ord(s[n-1])-67)&0xF]
        return ans	
                                                                       

题外话:
我们写的代码基本上是属于工程类的,这类的代码讲究的是可读性,那种刻意缩短代码行数,刻意为了一点点的性能提升而降低代码可读性的改动都是不好的。
如果不是对性能有极端的要求,我们更应该参考解法一中的代码。^_^

(全文完)

15 次阅读

发表评论

电子邮件地址不会被公开。