Roman to Integer

Roman to Integer

 

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

Naive Way:先写几个例子：
Roman   Integer
I              1

II          2

III         3

IV         4

V          5 

VI        6

VII       7

VIII      8

IX         9

X         10

L          50

C         100

D         500

M        1000

 

可以用一个数组先存字母。

一个级别低的字母出现在级别高的左边就是减，右边就是加。 

使用了一个Map，便于比较等级，算法复杂度O(n)，spaceO(1)。

public class Solution {
    private static final char[] syms = {'I','V','X','L','C','D','M'};
    private static final int[] val = {1,5,10,50,100,500,1000};
    public int romanToInt(String s) {
        int rlst = 0;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i = 0;i < syms.length;i++)
            map.put(syms[i], i);
        for(int i = 0;i < s.length()-1;i++)
            rlst += map.get(s.charAt(i)) < map.get(s.charAt(i+1))?-val[map.get(s.charAt(i))]:val[map.get(s.charAt(i))];
        rlst += val[map.get(s.charAt(s.length()-1))];
        return rlst;
    }
}

 

 

Improved Way:看了别人的算法，发现自己的两个数组跟这个map相当冲突。

应该直接把字母map成value，这样就保存等级，又保存value了。

 

public class Solution {
    private static final char[] syms = {'I','V','X','L','C','D','M'};
    private static final int[] val = {1,5,10,50,100,500,1000};
    public int romanToInt(String s) {
        int rlst = 0;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i = 0;i < syms.length;i++)
            map.put(syms[i], val[i]);
        for(int i = 0;i < s.length()-1;i++)
            rlst += map.get(s.charAt(i)) < map.get(s.charAt(i+1))?-map.get(s.charAt(i)):map.get(s.charAt(i));
        rlst += map.get(s.charAt(s.length()-1));
        return rlst;
    }
}