Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
思路：
- 首先找到Roman字母的规律
罗马数字的表示：
I - 1
V - 5
X - 10
L - 50
C - 100
D - 500
M - 1000
罗马数字采用七个罗马字母作数字、即Ⅰ（1）、X（10）、C（100）、M（1000）、V（5）、L（50）、D（500）。记数的方法：
- 相同的数字连写，所表示的数等于这些数字相加得到的数，如 Ⅲ=3；
- 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 Ⅷ=8、Ⅻ=12；
- 小的数字（限于 Ⅰ、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 Ⅳ=4、Ⅸ=9；
思路：
- 将罗马数字转换成对应的整数。首先将罗马数字翻转，从小的开始累加，如果遇到CM（M-C=1000-100=900）这种该怎么办呢？因为翻转过来是MC，M=1000先被累加，所以使用一个last变量，把M记录下来，如果下一个数小于M，那么减两次C，然后将C累加上
- 从右向左依次处理：当遇到这个字母表示的数字比后一个小的时候，减去这个数；否则，累加。
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
d = {'I':1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
s = s[::-1]
sum = 0
last = None
for e in s:
if last and d[e] < last:
sum -= 2*d[e]
sum += d[e]
last = d[e]
return sum
def romanToInt2(self, s):
d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
sum = 0
for i in xrange(len(s)-1, -1, -1):
if (i <len(s)-1) and (d[s[i]] < d[s[i+1]]):
sum -= d[s[i]]
else:
sum += d[s[i]]
return sum
if __name__ == '__main__':
sol = Solution()
s1 = "MCMLXXX"
print sol.romanToInt(s1)
print sol.romanToInt2(s1)
s2 = "DCXXI"
print sol.romanToInt(s2)
print sol.romanToInt2(s2)
s3 = "XIX"
print sol.romanToInt(s3)
print sol.romanToInt2(s3)
s3 = "CDMX"
print sol.romanToInt(s3)
print sol.romanToInt2(s3)
