LeetCode第[13]题(Java)：Roman to Integer

题目：罗马数字转换

题目难度：easy

题目内容：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.

翻译：

例如，2在罗马数字中被写成II，就是两个加在一起。12是写成，XII，也就是X+II。数字二十七是二十七，也就是XX+V+II。

罗马数字通常从左到右写得最大。然而，4的数字不是IIII。相反，数字4被写成IV，因为1在5之前减去它等于4。同样的原则也适用于9号，它被写成IX。有六种情况下使用减法：

I可以在V（5）和X（10）之前放置分别是4和9。

X可以放在L（50）和C（100）之前，分别是40和90。

C可以放置在D（500）和M（1000）之前，分别是400和900。

给定一个罗马数字，把它转换成整数。输入在从1到3999的范围内。

思路：

加法直接加，减法只匹配前后两个字符，所以当cur字符小于下一个字符的时候，使用减法。

用一个Map将各个字符与对应值都存进去，即可进行比较和取值

MyCode：

 1     public int romanToInt(String s) {
 2         if (s == null || s.isEmpty()) {
 3             return -1;
 4         }
 5         
 6         char[] sChar = s.toCharArray();
 7         Map<Character, Integer> map = new HashMap<Character, Integer>();
 8         map.put('I', 1);
 9         map.put('V', 5);
10         map.put('X', 10);
11         map.put('L', 50);
12         map.put('C', 100);
13         map.put('D', 500);
14         map.put('M', 1000);
15         
16         int sum=0;
17         for(int i=0;i<sChar.length-1;i++){
18             if(map.get(sChar[i]) < map.get(sChar[i+1]))
19                 sum-=map.get(sChar[i]); // 当前字符比下一个小，则总和减去此数字
20             else
21                 sum+=map.get(sChar[i]); // 否则直接加上
22         }
23         return sum+map.get(sChar[sChar.length-1]); // 因为最后一个没判断，并且无后续，所以必然是加
24     }

结果：Accept

参考答案：

 1  public int romanToInt(String s) {
 2     int nums[]=new int[s.length()];
 3     for(int i=0;i<s.length();i++){
 4         switch (s.charAt(i)){
 5             case 'M':
 6                 nums[i]=1000;
 7                 break;
 8             case 'D':
 9                 nums[i]=500;
10                 break;
11             case 'C':
12                 nums[i]=100;
13                 break;
14             case 'L':
15                 nums[i]=50;
16                 break;
17             case 'X' :
18                 nums[i]=10;
19                 break;
20             case 'V':
21                 nums[i]=5;
22                 break;
23             case 'I':
24                 nums[i]=1;
25                 break;
26         }
27     }
28     int sum=0;
29     for(int i=0;i<nums.length-1;i++){
30         if(nums[i]<nums[i+1])
31             sum-=nums[i];
32         else
33             sum+=nums[i];
34     }
35     return sum+nums[nums.length-1];
36 }

答案思路：此处直接将原来的字符数组（字符串）转换成相对应的int数组，这样就不需要一个map了，相对来说这种方法的访问更加简便，但是增加了一轮算法复杂度，不过map的访问要比直接数组访问多一个步骤，所以两者复杂度算下来可能差不多都是O（2n）的样子，而答案这种操作更加简单一些，可以借鉴。