题目描述（简单难度）

13. Roman to Integer - 图1

和上一道题相反，将罗马数字转换成阿拉伯数字。

解法一

先来一种不优雅的，也就是我开始的想法。就是遍历字符串，然后转换就可以，但同时得考虑 IV，IX 那些特殊情况。

  1. public int getInt(char r) {
  2.         int ans = 0;
  3.         switch (r) {
  4.         case 'I':
  5.             ans = 1;
  6.             break;
  7.         case 'V':
  8.             ans = 5;
  9.             break;
  10.         case 'X':
  11.             ans = 10;
  12.             break;
  13.         case 'L':
  14.             ans = 50;
  15.             break;
  16.         case 'C':
  17.             ans = 100;
  18.             break;
  19.         case 'D':
  20.             ans = 500;
  21.             break;
  22.         case 'M':
  23.             ans = 1000;
  24.         }
  25.         return ans;
  26.     }
  28.     public int getInt(char r, char r_after) {
  29.         int ans = 0;
  30.         switch (r) {
  31.         case 'I':
  32.             ans = 1;
  33.             break;
  34.         case 'V':
  35.             ans = 5;
  36.             break;
  37.         case 'X':
  38.             ans = 10;
  39.             break;
  40.         case 'L':
  41.             ans = 50;
  42.             break;
  43.         case 'C':
  44.             ans = 100;
  45.             break;
  46.         case 'D':
  47.             ans = 500;
  48.             break;
  49.         case 'M':
  50.             ans = 1000;
  51.             break;
  52.         }
  53.         if (r == 'I') {
  54.             switch (r_after) {
  55.             case 'V':
  56.                 ans = 4;
  57.                 break;
  58.             case 'X':
  59.                 ans = 9;
  60.             }
  61.         }
  62.         if (r == 'X') {
  63.             switch (r_after) {
  64.             case 'L':
  65.                 ans = 40;
  66.                 break;
  67.             case 'C':
  68.                 ans = 90;
  69.             }
  70.         }
  71.         if (r == 'C') {
  72.             switch (r_after) {
  73.             case 'D':
  74.                 ans = 400;
  75.                 break;
  76.             case 'M':
  77.                 ans = 900;
  78.             }
  79.         }
  80.         return ans;
  82.     }
  84.     public boolean isGetTwoInt(char r, char r_after) {
  85.         if (r == 'I') {
  86.             switch (r_after) {
  87.             case 'V':
  88.                 return true;
  89.             case 'X':
  90.                 return true;
  91.             }
  92.         }
  93.         if (r == 'X') {
  94.             switch (r_after) {
  95.             case 'L':
  96.                 return true;
  97.             case 'C':
  98.                 return true;
  99.             }
  100.         }
  101.         if (r == 'C') {
  102.             switch (r_after) {
  103.             case 'D':
  104.                 return true;
  105.             case 'M':
  106.                 return true;
  107.             }
  108.         }
  109.         return false;
  111.     }
  113.     public int romanToInt(String s) {
  114.         int ans = 0;
  115.         for (int i = 0; i < s.length() - 1; i++) {
  116.             ans += getInt(s.charAt(i), s.charAt(i + 1));
  117.             //判断是否是两个字符的特殊情况
  118.             if (isGetTwoInt(s.charAt(i), s.charAt(i + 1))) {
  119.                 i++;
  120.             }
  121.         }
  122.         //将最后一个字符单独判断，如果放到上边的循环会越界
  123.         if (!(s.length() >= 2 && isGetTwoInt(s.charAt(s.length() - 2), s.charAt(s.length() - 1)))) {
  124.             ans += getInt(s.charAt(s.length() - 1));
  125.         }
  127.         return ans;
  128.     }

时间复杂度：O（n），n 是字符串的长度。

空间复杂度：O（1）。

下边分享一些优雅的。

解法二

https://leetcode.com/problems/roman-to-integer/description/

  1. public int romanToInt(String s) {
  2.      int sum=0;
  3.     if(s.indexOf("IV")!=-1){sum-=2;}
  4.     if(s.indexOf("IX")!=-1){sum-=2;}
  5.     if(s.indexOf("XL")!=-1){sum-=20;}
  6.     if(s.indexOf("XC")!=-1){sum-=20;}
  7.     if(s.indexOf("CD")!=-1){sum-=200;}
  8.     if(s.indexOf("CM")!=-1){sum-=200;}
  10.     char c[]=s.toCharArray();
  11.     int count=0;
  13.    for(;count<=s.length()-1;count++){
  14.        if(c[count]=='M') sum+=1000;
  15.        if(c[count]=='D') sum+=500;
  16.        if(c[count]=='C') sum+=100;
  17.        if(c[count]=='L') sum+=50;
  18.        if(c[count]=='X') sum+=10;
  19.        if(c[count]=='V') sum+=5;
  20.        if(c[count]=='I') sum+=1;
  22.    }
  24.    return sum;
  26. }

把出现的特殊情况，提前减了就可以。

时间复杂度：O（1）。

空间复杂度：O（1）。

解法三

https://leetcode.com/problems/roman-to-integer/discuss/6509/7ms-solution-in-Java.-easy-to-understand

利用到罗马数字的规则，一般情况是表示数字大的字母在前，数字小的字母在后，如果不是这样，就说明出现了特殊情况，此时应该做减法。

  1.  private int getVal(char c){
  2.         switch (c){
  3.             case 'M':
  4.                 return 1000;
  5.             case 'D':
  6.                 return 500;
  7.             case 'C':
  8.                 return 100;
  9.             case 'L':
  10.                 return 50;
  11.             case 'X' :
  12.                 return 10;
  13.             case 'V':
  14.                 return 5;
  15.             case 'I':
  16.                 return 1;
  17.         }
  18.         throw new IllegalArgumentException("unsupported character");
  19.     }
  21.     public int romanToInt(String s) {
  22.         int res = 0;
  23.         if(s.length() == 0) return res;
  24.         for (int i = 0; i < s.length() - 1; i++) {
  25.             int cur = getVal(s.charAt(i));
  26.             int nex = getVal(s.charAt(i+1));
  27.             if(cur < nex){
  28.                 res -= cur;
  29.             }else{
  30.                 res += cur;
  31.             }
  32.         }
  33.         return res + getVal(s.charAt(s.length()-1));
  34.     }

时间复杂度：O（1）。

空间复杂度：O（1）。

总

这道题也不难，自己一开始没有充分利用罗马数字的特点，而是用一些 if，switch 语句判断是否是特殊情况，看起来就很繁琐了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情