代码git：History for 13. 罗马数字转整数.py - WankkoRee/LeetCodeAnswersWithPython3
因为室友先写了这题，所以我也来康康这题是个啥。
题目大概意思就是说把罗马数转成阿拉伯数，主要思路的话就是顺序遍历然后累加，但是需要注意某些数不能直接累加的问题。
比如说最理想的大数直接累加，如MMMDCCCLXXXVIII，其计算方式就是1000+1000+1000+500+100+100+100+50+10+10+10+5+1+1+1=3888，不用考虑IV=4、IX=9、XL=40、XC=90、CD=400、CM=900这种不能累加的情况。
而对于不能累加的这几个数的情况，我的思路是进行递归回溯，如果上一个罗马字母与本次罗马字母拼接出现了这些情况，就回溯然后重新计算正确是数字。（思路来自于计算机组成原理的定点除法算法之一——加减交替法）
写出代码如下：
class Solution:
def __solve(self, s: str, residue: str) -> (bool, int):
if s == '':
return True, 0
x = 0
if s[0] == 'M': # M 1000,MM 2000,MMM 3000
if residue in {'C'}: # CM 900
return False, 900
x += 1000
b, y = self.__solve(s[1:], s[0])
assert b
return True, x + y
elif s[0] == 'D': # D 500,DC 600,DCC 700,DCCC 800
if residue in {'C'}: # CD 400
return False, 400
x += 500
b, y = self.__solve(s[1:], s[0])
assert b
return True, x + y
elif s[0] == 'C': # C 100, CC 200, CCC 300
if residue in {'X'}: # XC 90
return False, 90
x += 100
b, y = self.__solve(s[1:], s[0])
if b:
return True, x + y
else: # CD 400, CM 900
x -= 100
x += y
b, y = self.__solve(s[2:], s[0])
assert b
return True, x + y
elif s[0] == 'L': # L 50, LX 60, LXX 70, LXXX 80
if residue in {'X'}: # XL 40
return False, 40
x += 50
b, y = self.__solve(s[1:], s[0])
assert b
return True, x + y
elif s[0] == 'X': # X 10, XX 20, XXX 30
if residue in {'I'}: # IX 9
return False, 9
x += 10
b, y = self.__solve(s[1:], s[0])
if b:
return True, x + y
else: # XL 40, XC 90
x -= 10
x += y
b, y = self.__solve(s[2:], s[0])
assert b
return True, x + y
elif s[0] == 'V': # V 5, VI 6, VII 7, VIII 8
if residue in {'I'}: # IV 4
return False, 4
x += 5
b, y = self.__solve(s[1:], s[0])
assert b
return True, x + y
elif s[0] == 'I': # I 1, II 2, III 3
x += 1
b, y = self.__solve(s[1:], s[0])
if b:
return True, x + y
else: # IV 4, IX 9
x -= 1
x += y
b, y = self.__solve(s[2:], s[0])
assert b
return True, x + y
return True, x
def romanToInt(self, s: str) -> int:
return self.__solve(s, '')[1]
solution = Solution()
assert solution.romanToInt("III") == 3
assert solution.romanToInt("IV") == 4
assert solution.romanToInt("IX") == 9
assert solution.romanToInt("LVIII") == 58
assert solution.romanToInt("MCMXCIV") == 1994其中__solve(self, s: str, residue: str) -> (bool, int)是递归函数，s用来传输剩余罗马字符串，residue用来传输上一个罗马字母（其实正确名称应该是prev，当时不知道咋回事写了个residue上去），而返回的话是个tuple，0位表示是否需要回溯，若回溯则1位是回溯后需要正确累加的数，若无需回溯则1位是剩余的罗马字符串所表示的阿拉伯数。
以题目中的样例MCMXCIV为例，若使用这个思路去计算的话，流程应当是M+C-C+CM+X-X+XC+I-I+IV，即1000+100-100+900+10-10+90+1-1+4=1994。
提交跑一下测试数据，一次AC？！
执行用时：
36 ms, 在所有Python3提交中击败了96.41%的用户
内存消耗：15 MB, 在所有Python3提交中击败了72.20%的用户
通过测试用例：3999 / 3999
那看看能不能优化一下，于是把没必要存在的x相关运算给删了，结果时间还增加了...应该是leetcode的锅。
执行用时：
52 ms, 在所有Python3提交中击败了37.03%的用户
内存消耗：15.2 MB, 在所有Python3提交中击败了5.24%的用户
通过测试用例：3999 / 3999
室友的思路完全总体上一样，也是顺序遍历累加，不过并不是回溯错误数据，而是直接先判断两位的情况有没有可能是特殊情况，再判断正常情况进行累加。
看了下力扣这题的评论区，直接右比左小等+、大-就行了，我是个憨批。
Comments NOTHING