Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
思路：
- 首先找到Roman字母的規(guī)律
羅馬數(shù)字的表示：
I - 1
V - 5
X - 10
L - 50
C - 100
D - 500
M - 1000
羅馬數(shù)字采用七個羅馬字母作數(shù)字廉涕、即Ⅰ（1）泻云、X（10）、C（100）狐蜕、M（1000）宠纯、V（5）、L（50）层释、D（500）征椒。記數(shù)的方法：
- 相同的數(shù)字連寫，所表示的數(shù)等于這些數(shù)字相加得到的數(shù)湃累，如 Ⅲ=3勃救；
- 小的數(shù)字在大的數(shù)字的右邊，所表示的數(shù)等于這些數(shù)字相加得到的數(shù)治力，如 Ⅷ=8蒙秒、Ⅻ=12；
- 小的數(shù)字（限于 Ⅰ宵统、X 和 C）在大的數(shù)字的左邊晕讲，所表示的數(shù)等于大數(shù)減小數(shù)得到的數(shù)覆获，如 Ⅳ=4、Ⅸ=9瓢省；
思路：
- 將羅馬數(shù)字轉(zhuǎn)換成對應(yīng)的整數(shù)弄息。首先將羅馬數(shù)字翻轉(zhuǎn)，從小的開始累加勤婚，如果遇到CM（M-C=1000-100=900）這種該怎么辦呢摹量？因為翻轉(zhuǎn)過來是MC，M=1000先被累加馒胆，所以使用一個last變量缨称，把M記錄下來，如果下一個數(shù)小于M祝迂，那么減兩次C睦尽，然后將C累加上
- 從右向左依次處理：當(dāng)遇到這個字母表示的數(shù)字比后一個小的時候，減去這個數(shù)型雳；否則当凡，累加。
#!/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)
