LeetCode 罗马数 13. Roman to Integer

Bertha 。 2022-03-16 19:42 208阅读 0赞

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
    I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.  
X can be placed before L (50) and C (100) to make 40 and 90.  
C can be placed before D (500) and M (1000) to make 400 and 900.  
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:
    
    Input: "III"
    Output: 3
    Example 2:
    
    Input: "IV"
    Output: 4
    Example 3:
    
    Input: "IX"
    Output: 9
    Example 4:
    
    Input: "LVIII"
    Output: 58
    Explanation: L = 50, V= 5, III = 3.
    Example 5:
    
    Input: "MCMXCIV"
    Output: 1994
    Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

罗马数的特征上面已经说明了，对应关系见最上面的表，罗马数大小从左往右看。  
但是

*  I(1) 才能放在 V (5) 和 X (10)之前算成 4 和 9.
 *  X(10) 才能放在 L (50) 和 C (100)之前算成 40 和 90.
 *  C(100) 才能放在 D (500) 和 M (1000)之前算成 400 和 900.

大家发现这个规则的规律没有，**I和X前面最多只能放一个I，如果想表达3，不是IIV而是III，想表达8，不是IIX而是VIII；同理L和C，D和M也是一样的。**即左边小的数不能连着超过一次。这个规律十分重要。**如果左边的罗马数小于等于右边的罗马数，则是左边罗马数加上右边罗马数；如果左边的罗马数大于右边的罗马数,则用当前已经计算的值加上右边大的罗马数减去两倍的左边小的罗马数**（可以观察上面的例子）。

罗马数实际上是字符串，首先我们必须遍历罗马数，其次要知道每次遍历到的罗马数对应的是数字几，可以使用switch，也可以使用HashMap来存储罗马数与整数对应关系。

class Solution { 
        public int romanToInt(String s) { 
          Map<Character, Integer> 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);
          
          char[] sc = s.toCharArray();
          int total = map.get(sc[0]);
          int pre = map.get(sc[0]);
          for(int i = 1; i < sc.length; i++) { 
            int cur = map.get(sc[i]);
            
            if(cur <= pre) { 
            	total += cur;
            } else { 
            	total = total + cur - 2 * pre;
            } 
            pre = cur;
          }
          return total;
        }
    }

上面的规律还有另外一种解释：

<table> 
 <thead> 
  <tr> 
   <th>罗马数</th> 
   <th>字面值和真实值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>IV</td> 
   <td>I+V=6 真实值为6-2=4</td> 
  </tr> 
  <tr> 
   <td>IX</td> 
   <td>I+X=11 真实值为11-2=9</td> 
  </tr> 
  <tr> 
   <td>XL</td> 
   <td>X+L=60 真实值为60-20=40</td> 
  </tr> 
  <tr> 
   <td>XC</td> 
   <td>X+C=110 真实值为110-20=90</td> 
  </tr> 
  <tr> 
   <td>CD</td> 
   <td>C+D=600 真实值为600-200=400</td> 
  </tr> 
  <tr> 
   <td>CM</td> 
   <td>C+M=1100 真实值为1100-200=900</td> 
  </tr> 
 </tbody> 
</table>

即出现以上组合不论前面的值是多少，加上上面的组合都会先减去2，减去20，减去200。例如XIV是14，其实是等于X+I+V-2=16-2=14

class Solution { 
        public int romanToInt(String s) { 
             int sum=0;
            if(s.indexOf("IV")!=-1){ sum-=2;}
            if(s.indexOf("IX")!=-1){ sum-=2;}
            if(s.indexOf("XL")!=-1){ sum-=20;}
            if(s.indexOf("XC")!=-1){ sum-=20;}
            if(s.indexOf("CD")!=-1){ sum-=200;}
            if(s.indexOf("CM")!=-1){ sum-=200;}
    
            char c[]=s.toCharArray();
            int count=0;
    
           for(;count<=s.length()-1;count++){ 
               if(c[count]=='M') sum+=1000;
               if(c[count]=='D') sum+=500;
               if(c[count]=='C') sum+=100;
               if(c[count]=='L') sum+=50;
               if(c[count]=='X') sum+=10;
               if(c[count]=='V') sum+=5;
               if(c[count]=='I') sum+=1;
    
           }
           return sum;
        }
    }