leetcode: Roman to Integer

问题描述：

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

原问题链接：https://leetcode.com/problems/roman-to-integer/

 

问题分析

    在前面的文章中已经提到过罗马数字的组成规则。它本质上是由有限的单个字符组成。针对不同的位以及重复次数限制来组成别的数字。它们基本的字符无非就是如下几个：

I: 1    V: 5    X: 10    L: 50    C: 100    D: 500    M: 1000

    所以给定一个罗马数字，无非就是要将一串罗马数字给解析成对应的阿拉伯数字并将结果加起来。这里该如何对给定的罗马数字串解析就是问题的核心。在罗马数字的表示方法里，对于像4, 9之类的数字不管在个位十位百位等，它们都是一个小的数字放在一个大的数字前面。而对于其他的数字情况，无非就是几个重复的数字。所以，当给定一个当前的罗马数字，如果它比它后面的数字小，则应该将它们放在一起解析。否则就单独解析，然后加起来就可以了。因为我们是一个字符一个字符的解析，对于出现前面一个数字不小于后面的就直接相加，而否则的情况则要减一个对应的值。而为了描述这个计算，我们可以将单个的罗马数字符和对应的阿拉伯数字映射起来。在具体的实现里可以用一个map来保存。

    这样我们就得到一个如下的实现：

 

public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) return -1;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        if(s.length() == 1) return map.get(s.charAt(0));
        int result = 0;
        for (int i = 1; i < s.length(); i++) {
            if (map.get(s.charAt(i - 1)) >= map.get(s.charAt(i)))
                result += map.get(s.charAt(i - 1));
            else
                result -= map.get(s.charAt(i - 1));
        }
        result += map.get(s.charAt(s.length() - 1));
        return result;
    }
}

     在这个实现里要考虑到串长度为1的情况。另外，针对和前一个字符的比较，我们需要把最后的那个字符给加进来以免遗漏。这个方法的实现看起来很简单，但是实际执行效率并不是很高。为什么会这样呢？因为我们这里是建立的字符到Integer整数的映射。但是每次访问解析的时候要将值做一个boxing, unboxing的操作。这样将极大的降低执行的效率。这其实也是java语言本身的一些限制导致的。

    没办法，如果要想让上述的代码再快一点，可以将字符串的映射转换成一个函数，然后用一大堆的判断语句来返回结果。这样会快不少。因为比较简单，这种实现就不赘述了。