LeetCode刷题之旅简单篇13-Roman-to-Integer罗马数字转整数

42次阅读

共计 2759 个字符，预计需要花费 7 分钟才能阅读完成。

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.

来，我们来看看一个把故事搞复杂了的人：
字符串 + 一开始不确定 + 一个一个加字符，然后每次值都要重新算
好！
我们来一个动态规划吧~ >-< ~
然后呢，我就鼓捣了快一个小时，推了半天公式，然后还在想为什么 LeetCode 上一道简单题还要用动规还这么难推，心里隐隐约约觉得自己把问题搞复杂了。
万幸的是我居然还做出来了（原谅我真的不想打推的一堆式子，还需努力啊）：

class Solution {public int romanToInt(String s) {List<Integer> array = new ArrayList<Integer>();
        // 先将字符串转换为数组
        for(int i = 0; i < s.length(); i++){switch (s.charAt(i)){case 'I' : array.add(1);break;
                case 'V' : array.add(5);break;
                case 'X' : array.add(10);break;
                case 'L' : array.add(50);break;
                case 'C' : array.add(100);break;
                case 'D' : array.add(500);break;
                case 'M' : array.add(1000);break;
                default:return 0;
            }
        }
        if(array.size()==1){return array.get(0);
        }
        int ind_sure = 0;
        int result = 0;
        int r_sure = 0;
        int temp = array.get(0);
        for(int i = 1; i < array.size();i++){if(array.get(i - 1) < array.get(i)){temp = temp + array.get(i) - 2*array.get(i-1);
                result = r_sure + temp;
            }
            if(array.get(i - 1) >= array.get(i)){
                r_sure = r_sure + temp;
                temp = array.get(i);
                result = r_sure + temp;
            }
        }
        return result;
    }
}

执行用时 :6 ms, 在所有 Java 提交中击败了 53.88% 的用户
内存消耗 :40 MB, 在所有 Java 提交中击败了 5.56% 的用户

其实上面解法的问题是对于题目的规律把控地还不准确，我理解为，代表值比较小的罗马数字出现在代表值比较大的罗马数字之前，就意味着要做减法；但事实上是，只要一个罗马数字后一个罗马数字比前面的大，那就意味着这个罗马数字需要被减掉。比如对于 IXVIM 来说，只要发现了 X 比I大，那不管 X 后是什么，这个 I 都代表着 -1；而只要有V 在I之前，这个 V 都是正的。
所以，对于 i 位置上的罗马数字，我们只需要看往后一个字符 i+1 位置上的罗马数字即可：

class Solution {public int romanToInt(String s) {List<Integer> array = new ArrayList<Integer>();
        // 先将字符串转换为数组
        for(int i = 0; i < s.length(); i++){switch (s.charAt(i)){case 'I' : array.add(1);break;
                case 'V' : array.add(5);break;
                case 'X' : array.add(10);break;
                case 'L' : array.add(50);break;
                case 'C' : array.add(100);break;
                case 'D' : array.add(500);break;
                case 'M' : array.add(1000);break;
                default:return 0;
            }
        }

        int result = 0;
        int i = 0;
        for(i = 0; i < array.size() - 1; i++){if(array.get(i) < array.get(i + 1)){result = result - array.get(i);
            } else {result = result + array.get(i);
            }
        }
        result = result + array.get(i);
        return result;
    }
}

执行结果：