[刷题]LeetCode 13. 罗马数字转整数

发布于 2021-10-06  0 次阅读

代码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

室友的思路完全总体上一样，也是顺序遍历累加，不过并不是回溯错误数据，而是直接先判断两位的情况有没有可能是特殊情况，再判断正常情况进行累加。

看了下力扣这题的评论区，直接右比左小等+、大-就行了，我是个憨批。

The End