Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
I = 1;
V = 5;
X = 10;
L = 50;
C = 100;
D = 500;
M = 1000;
参考C++：http://www.cnblogs.com/easonliu/p/3654182.html
-
个位数举例Ⅰ,1 】Ⅱ，2】 Ⅲ，3】 Ⅳ，4 】Ⅴ，5 】Ⅵ，6】Ⅶ，7】 Ⅷ，8 】Ⅸ，9 】
-
十位数举例Ⅹ，10】 Ⅺ，11 】Ⅻ，12】 XIII,13】 XIV,14】 XV,15 】XVI,16 】XVII,17 】XVIII,18】 XIX,19】 XX,20】 XXI,21 】XXII,22 】XXIX,29】 XXX,30】 XXXIV,34】 XXXV,35 】XXXIX,39】 XL,40】 L,50 】LI,51】 LV,55】 LX,60】 LXV,65】 LXXX,80】 XC,90 】XCIII,93】 XCV,95 】XCVIII,98】 XCIX,99 】
-
百位数举例C,100】 CC,200 】CCC,300 】CD,400】 D,500 】DC,600 】DCC,700】 DCCC,800 】CM,900】 CMXCIX,999】
-
千位数举例M,1000】 MC,1100 】MCD,1400 】MD,1500 】MDC,1600 】MDCLXVI,1666】 MDCCCLXXXVIII,1888 】MDCCCXCIX,1899 】MCM,1900 】MCMLXXVI,1976】 MCMLXXXIV,1984】 MCMXC,1990 】MM,2000 】MMMCMXCIX,3999】
解释一下罗马计算的规律。当下一个的值大于前一个的值，就减去前一个值。如CD=500-100=400。
如下代码是我自己编写的，但是因为算法太大，导致Time Limit Exceeded。不过还是先记录下这个繁重的算法。
1 public class Solution { 2 public int romanToInt(String s) { 3 //String []value={"I","V","X","L","C","D","M"}; 4 char []value={'I','V','X','L','C','D','M'}; 5 int []a ={1,5,10,50,100,500,1000}; 6 int num=0; 7 for(int i=0;i<s.length();i++){ 8 for(int j=0;j<value.length;j++){ 9 if(s.charAt(i)==value[j]){ 10 if(i+1<s.length()){ 11 for(int k=0;k<value.length;k++){ 12 if(s.charAt(i+1)==value[k]){ 13 if(a[j]<a[k]) 14 //比较的是整型int值，而不是字符的大小，因而要转换 15 //if(s.charAt(i)<s.charAt(i+1)){ 16 num=num-a[j];//当后一个的值大于前一个值，减去前一个值 17 else 18 num=num+a[j]; 19 } 20 } 21 }else 22 num=num+a[j]; 23 } 24 25 } 26 27 } 28 System.out.println(num); 29 return num; 30 } 31 }
大神写出的高效率代码，先贴出来。如下：
1 public class Solution { 2 public int get(char c) { 3 char dict[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'}; 4 int value[] = {1, 5, 10, 50, 100, 500, 1000}; 5 int index = 0; 6 for (; index < dict.length; index++) { 7 if (dict[index] == c) 8 break; 9 } 10 return value[index]; 11 } 12 public int romanToInt(String s) { 13 int ret = 0; 14 for (int i = 0; i < s.length(); i++) { 15 char c = s.charAt(i); 16 int value = get(c); 17 if (i+1 < s.length()) { 18 int next = get(s.charAt(i+1)); 19 if (value < next) 20 ret -= value; 21 else 22 ret += value; 23 } else { 24 ret += value; 25 } 26 } 27 return ret; 28 } 29 }