Given a roman numeral, convert it to an integer.

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

关于罗马数字介绍（以下内容摘自维基百科）：

罗马数字共有7个，即Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、Ⅼ（50）、Ⅽ（100）、Ⅾ（500）和Ⅿ（1000）。按照下述的规则可以表示任意正整数。

• 重复数次：一个罗马数字重复几次，就表示这个数的几倍。

• 右加左减：
  • 在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
  • 在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
  • 左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
  • 但是，左减时不可跨越一个位值。比如，99不可以用IC（100 - 1）表示，而是用XCIX（（100 - 10） + （10 -  1））表示。
  • 左减数字必须为一位，比如8写成VIII，而非IIX。
  • 右加数字不可连续超过三位，比如14写成XIV，而非XIIII。

• 加线乘千：
  • 在罗马数字的上方加上一条横线或者加下标的Ⅿ，表示将这个数乘以1000，即是原数的1000倍。
  • 同理，如果上方有两条横线，即是原数的1000000倍。

• 数码限制：
  • 同一数码最多只能连续出现三次，如40不可表示为XXXX，而要表示为XL。

思路：题中数字范围为1-3999，因此不会出现加上划线的情况。利用左减数字必须为一位，即放在大数前面的小数只能有一个，因此在比较当前数字时，只需考虑其后面的一位。如果当前数字小于它后面的数字，则加上当前数字；否则就减去当前数字。

解法1：利用map接口，但时间复杂度高

 

public int romanToInt(String s){        int num = 0;        char[] chars = s.toCharArray();        Map
     
       map = new HashMap<>();        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);        for(int i = 0; i < chars.length; i++){            if(i == chars.length - 1 || map.get(chars[i]) >= map.get(chars[i + 1]))                num += map.get(chars[i]);            else                num -= map.get(chars[i]);        }        return num;    }
     

 

解法2：

public int romanToInt(String s){        int num = 0;        int current;        char[] chars = s.toCharArray();        for(int i = 0; i < chars.length; i++){            current = charToInt(chars[i]); 　　　　　　　　//如果当前数字是最后一个数字，或当前数字大于它后面的数字，则加上当前数字            if(i == chars.length - 1 || current >= charToInt(chars[i + 1]))                num += current; 　　　　　　　　//如果当前数字小于它后面的数字,则减去当前数字            else                num -= current;        }        return num;    }    public int charToInt(char ch){        int data = 0;        switch(ch){        case 'I':             data = 1;            break;        case 'V':             data = 5;            break;        case 'X':             data = 10;            break;        case 'L':             data = 50;            break;        case 'C':             data = 100;            break;        case 'D':             data = 500;            break;        case 'M':             data = 1000;            break;        }        return data;    }

解法3：从前往后遍历字符串，每次都加上其相应的数字；如果当前数字大于它前面的数字，则减去前面数字的二倍

public int romanToInt(String s){        int num = charToInt(s.charAt(0)), cur, pre;        for(int i = 1; i < s.length(); i++){            cur = charToInt(s.charAt(i));            pre = charToInt(s.charAt(i - 1)); 　　　　     num += cur; //加上当前数字 　　　　　　　//如果当前数字大于它前面的数字，则减去前面数字的二倍            if(pre < cur)                num -= 2 * pre;        }        return num;    }public int charToInt(char ch){        int data = 0;        switch(ch){        case 'I':             data = 1;            break;        case 'V':             data = 5;            break;        case 'X':             data = 10;            break;        case 'L':             data = 50;            break;        case 'C':             data = 100;            break;        case 'D':             data = 500;            break;        case 'M':             data = 1000;            break;        }        return data;    }