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 – 1

• 否则，将当前值加入到结果中，然后开始下一段记录。比如VI = 5 + 1， II=1+1

找下subtractive notation的规律，以简单的例子s = IX 说明。

1. 如果按照additive性质的话应该ret = 1+10 = 11。但因为num(X)=10>num(I)=1，ret = 10 - 1。

2. 将subtractive rule转换成等效的additive rule：ret = 1 + (10 - 2*1)

建立一个罗马字符对应整数的hash table ht。

当ht[s[i]] > ht[s[i-1]]，即为subtractive notation：ret += (ht[s[i]] - 2*ht[s[i-1]]), 否则为additive nontation：ret+=ht[s[i]]

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
        result = 0
        for i in xrange(len(s)):
            result += roman[s[i]]
            if i != 0 and roman[s[i]] > roman[s[i-1]]:
                result -= 2*roman[s[i-1]]
        return result