Easy 4 – 罗马数字转整数

把给出的罗马数字转换成整数。

首先来看我的第一版:

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_number = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        number = 0
        for number, character in enumerate(s):
            while number < len(s)-1:
                if roman_number[character] < roman_number[s[number+1]]:
                    number -= roman_number[character]
                number += roman_number[character]
            number += roman_number[character]
        return number

我甚至不知道它是对是错,因为leetcode告诉我它超出时间限制了。不过,使用词典来存储数据的方向应该是对的。大概的方法论就是比较前一个数和后一个数的大小,如果比后面的小,那就把这个数转成负数和后面的数相加。

然后按照这个思路重新写了一个:

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_number = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        trans_number = []
        for character in s:
            trans_number.append(roman_number[character])
        length = len(trans_number)
        for location, number in enumerate(trans_number):
            if location+1 != length:
                if number < trans_number[location+1]:
                    trans_number[location] = -number
        add = 0 
        for number in trans_number:
            add += number
        return add

这次确实通过了,但是内存的消耗非常大,只击败了7%的用户。

哦我这该死的胜负欲,明天看看有没有别的解法,先睡觉了。

今天想了想为啥内存消耗会变大,可能是因为我又引入了一个trans_number。随后做了一下更改:

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_number = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        add = 0
        for location, char in enumerate(s):
            if location < len(s) - 1:
                if roman_number[char] < roman_number[s[location+1]]:
                    add -= roman_number[char]
                else:
                    add += roman_number[char]
            else:
                add += roman_number[s[-1]]
        return add

这样的话内存消耗减少了很多,显示超过了89.88%的用户,但是执行用时增加了很多,应该是因为每次循环都需要对s进行一系列操作导致的。

Leave a Reply