13 Roman to Integer

Given a roman numeral, convert it to an integer.

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

 整体来说，罗马数字中的字符代表的数值大小，一般是从左至右非严格递减的（也就是说可能相邻的两个字符相等），然后不停地累加就行了。但如果发生相邻的两个元素，左边的字符比右边的字符代表的数值小，就需要减去左右这个字符代表的数值。如IV就是5-4=1，所以CIV就是100-1+5=104。

public class Solution {  
    private int[] val = new int[255];  
    private void init() {  
        val['I'] = 1; val['V'] = 5; val['X'] = 10; val['L'] = 50;  
        val['C'] = 100; val['D'] = 500; val['M'] = 1000;  
    }  
  
    public int romanToInt(String s) {  
        init();  
        int ret = 0;  
        for (int i = 0; i < s.length(); i++) {  
            if (i > 0 && val[s.charAt(i)] > val[s.charAt(i - 1)]) {  
                ret += val[s.charAt(i)] - 2 * val[s.charAt(i - 1)];  
            } else {  
                ret += val[s.charAt(i)];  
            }  
        }  
        return ret;  
    }  
}  

解题思路：将罗马数字转换成对应的整数。首先将罗马数字翻转，从小的开始累加，如果遇到CM（M-C=1000-100=900）这种该怎么办呢？因为翻转过来是MC，M=1000先被累加，所以使用一个last变量，把M记录下来，如果下一个数小于M，那么减两次C，然后将C累加上，这个实现比较巧妙简洁。

class Solution:
    # @return an integer
    def romanToInt(self, s):
        numerals = { "M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1 }
        sum=0
        s=s[::-1]
        last=None
        for x in s:
            if last and numerals[x]<last:
                sum-=2*numerals[x]
            sum+=numerals[x]
            last=numerals[x]
        return sum