站点图标 Wankko Ree's Blog

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

代码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=4IX=9XL=40XC=90CD=400CM=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
退出移动版