LeetCode: Roman to Integer 解题报告

Roman to Integer
Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

SOLUTION 1：

思路：

从后往前遍历罗马数字，如果某个数比前一个数小，则把该数在结果中减掉；
反之，则在结果中加上当前这个数；

 1 package Algorithms.string;
 2 
 3 public class RomanToInt {
 4     public int romanToInt(String s) {
 5         if (s == null) {
 6             return 0;
 7         }
 8         
 9         int len = s.length();
10         int sum = 0;
11         int pre = 0;
12         
13         for (int i = len - 1; i >= 0; i--) {
14             int cur = romanTable(s.charAt(i));
15             
16             if (i == len - 1) {
17                 // 如果是在尾部，直接加上当前值
18                 sum += cur;
19             } else {
20                 // 判定当前值是不是比前一个值要小，如果小，则需要减去它
21                 if (cur < pre) {
22                     sum -= cur;
23                 } else {
24                     sum += cur;
25                 }
26             }
27             pre = cur;
28         }
29         
30         return sum;
31     }
32     
33     public int romanTable(char c) {
34         int num = 0;
35         switch(c) {
36             case 'I':
37                 num = 1;
38                 break;
39             case 'V':
40                 num = 5;
41                 break;
42             case 'X':
43                 num = 10;
44                 break;
45             case 'L':
46                 num = 50;
47                 break;
48             case 'C':
49                 num = 100;
50                 break;
51             case 'D':
52                 num = 500;
53                 break;
54             case 'M':
55                 num = 1000;
56                 break;
57             default:
58                 num = 0;
59                 break;
60         }
61         
62         return num;
63     }
64 }

View Code

SOLUTION 2:

除了用函数转换，也可以用map来转换。

 1 public int romanToInt(String s) {
 2         if (s == null) {
 3             return 0;
 4         }
 5         
 6         // bug 1: forget new.
 7         HashMap<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 len = s.length();
17         int num = 0;
18         for (int i = len - 1; i >= 0; i--) {
19             int cur = map.get(s.charAt(i));
20             if (i < len - 1 && cur < map.get(s.charAt(i + 1))) {
21                 num -= cur;
22             } else {
23                 num += cur;
24             }
25         }
26         
27         return num;
28     }

View Code

GITHUB 代码：

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/RomanToInt.java