题目
给定一个罗马数字，将它转换为一个整数。输入保证在1到3999的范围内。
解决思路
在解决该题前，得先明白什么罗马数字以及它转化为数字的一些规则：
罗马数字共有7个，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）
规则：
1、重复数次：一个罗马数字重复几次，就表示这个数的几倍。
2、右加左减：
在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV但是，左减时不可跨越一个位数。比如，99不可以用IC（100 - 1）表示，而是用XCIX（[100 - 10] + [10 - 1]）表示。（等同于阿拉伯数字每位数字分别表示。）左减数字必须为一位，比如8写成VIII，而非IIX。右加数字不可连续超过三位，比如14写成XIV，而非XIIII。3、加线乘千：
在罗马数字的上方加上一条横线或者加上下标的Ⅿ，表示将这个数乘以1000，即是原数的1000倍。同理，如果上方有两条横线，即是原数的1000000（1000^{2}）倍。4、数码限制：
同一数码最多只能出现三次，如40不可表示为XXXX，而要表示为XL。例外：由于IV是古罗马神话主神朱庇特（即IVPITER，古罗马字母里没有J和U）的首字，因此有时用IIII代替Ⅳ。本题的难点在于理解罗马数字的规则。对于这种复杂的题目，我们得一针见血，这些规则，对我们有用的就一个，即“右加左减”。简单理解，就是较小的数如果在较大的数右边，则表示加，如果在左边，则表示减。此外，左减数字必须为一位，右加数字不可连续超过三位。
那么，我们可以根据这个规则去解决这个问题。首先，我们肯定要存储罗马数字所表示的数字，其次，依次将所给定的罗马数字转化为数字并存储到数组中，然后，再依次遍历这个数组，如果左边的数小于右边的数，则对这个元素的值乘以-1。最后，依次累加数组的元素即可。
下面则是该思路的Java程序：
public int romanToInt(String s) { // 1.存储罗马数字的规则 Map romanMap = new HashMap(); romanMap.put('I',1); romanMap.put('V',5); romanMap.put('X',10); romanMap.put('L',50); romanMap.put('C',100); romanMap.put('D',500); romanMap.put('M',1000); // 2.将字符转化为数字 int[] ic = new int[s.length()]; for(int i = 0;i < s.length();i++){ ic[i] = (int)romanMap.get(s.charAt(i)); } // 3.按左加右减的规则转化数字 for(int i = 0;i < s.length();i++){ if(i != s.length() - 1 && ic[i] < ic[i+1]){ ic[i] = -ic[i]; } } // 4.依次累加每个数 int sum = 0; for(int i = 0;i < s.length();i++){ sum += ic[i]; } return sum; }由程序可以看出，该算法的时间复杂度最大为O(n)，空间复杂度为O(n)。
