Leetcode 13. Roman numeral to integer

Power button | # 13. Roman numeral to integer

Title screenshot

First, use a dictionary to correspond roman numbers to numbers

romaNumberMap = {
            "I" : 1,
            "V" : 5,
            "X" : 10,
            "L" : 50,
            "C" : 100,
            "D" : 500,
            "M" : 1000,
        }

And then use it enumerate() Function will need to study the string str Traverse , Make each element have a subscript index .

enumerate() Function is used to traverse a data object ( As listing 、 Tuples or strings ) Combined into an index sequence , List both data and data index , Generally used in for Cycle of .

Python enumerate() function | Novice tutorial

Ideas ： Roman numerals if the value on the left is smaller than that on the right , Then the value is accumulated as a negative number . If the value on the left is larger or equal than that on the right , Direct accumulation .

Such as “X I V”,X=10, I = 1, V = 5.

                                X>I,    I<V,

So the result is equal to           +10      -1       +5    =14.

Such as “MCMXCIV”,M=1000, C=100, M=1000, X=10, C=100, I=1, V=5.

                               M>C,       C<M,        M>X,         X<C,     C>I,         I<V.

            The result is equal to the   +1000         -100        +1000        -10       +100        -1           +5   =  1994

The last one is accumulated directly without comparison .

class Solution:
    def romanToInt(self, s: str) -> int:
        romaNumberMap = {
            "I" : 1,
            "V" : 5,
            "X" : 10,
            "L" : 50,
            "C" : 100,
            "D" : 500,
            "M" : 1000,
        }
        n = len(s)
        sum =0
        for i, ch in enumerate(s):
            value = romaNumberMap[ch]
            if i < n-1 and value < romaNumberMap[s[i+1]]:
                sum -= value
            elif i < n-1 and value >= romaNumberMap[s[i+1]]:
                sum +=value
        sum +=value
        return sum


if __name__ == "__main__":
    a = Solution()
    print(a.romanToInt("MCMXCIV"))

Code optimization

After the sentence is judged, do not elif To determine , Direct use else Cover other situations .

class Solution:
    def romanToInt(self, s: str) -> int:
        romaNumberMap = {
            "I" : 1,
            "V" : 5,
            "X" : 10,
            "L" : 50,
            "C" : 100,
            "D" : 500,
            "M" : 1000,
        }
        n = len(s)
        sum =0
        for i, ch in enumerate(s):
            value = romaNumberMap[ch]
            if i < n-1 and value < romaNumberMap[s[i+1]]:
                sum -= value
            else:
                sum +=value
        return sum


if __name__ == "__main__":
    a = Solution()
    print(a.romanToInt("MCMXCIV"))

It can also be done without enumerate() function

This method is useless in, So after the cycle, it is still necessary to add sum += romaNumberMap[s[i+1]]

class Solution:
    def romanToInt(self, s: str) -> int:
        romaNumberMap = {
            "I" : 1,
            "V" : 5,
            "X" : 10,
            "L" : 50,
            "C" : 100,
            "D" : 500,
            "M" : 1000,
        }
        n = len(s)
        sum =0
        for i in range(0, n-1):
            if romaNumberMap[s[i]] < romaNumberMap[s[i+1]]:
                sum -= romaNumberMap[s[i]]
            else:
                sum +=romaNumberMap[s[i]]
        sum += romaNumberMap[s[i+1]]
        return sum


if __name__ == "__main__":
    a = Solution()
    print(a.romanToInt("MCMXCIV"))

Expand

You may encounter yourself in the interview enumerate() function

def my_enumerate(datas):
    for i in range(len(datas)):
        yield i, datas[i]

Python3 Iterators and generators | Novice tutorial

stay Python in , Used yield The function of the is called the generator （generator）..

Different from ordinary functions , A generator is a function that returns an iterator , Can only be used for iterative operations , It's easier to understand that a generator is an iterator .

During the call generator run , Every encounter yield Function will pause and save all current running information , return yield Value , And next time next() Method to continue from the current location .

Call a generator function , Returns an iterator object .

  See Python yield Use analysis | Novice tutorial

yield The role of ： Turn a function into a generator, with yield The function of is no longer a normal function ,Python The interpreter will treat it as a generator, Call function f(x) when , Not execute f function , It's back to a iterable object . stay for Loop execution , Every cycle will execute fab The code inside the function , Execute to yield b when ,f The function returns an iteration value , Next iteration , Code from yield xxx The next statement of continues to execute , The local variable of the function looks exactly the same as before the last interrupt , So the function continues , Until we meet again yield.

With a yield The function of is a generator, It's different from ordinary functions , Generate a generator It looks like a function call , But no function code is executed , Until you call next()（ stay for It's called automatically in the loop next()） Just started to execute . Although the execution process still follows the process of the function , But every time it gets to one yield The statement breaks , And return an iteration value , The next execution is from yield Continue with the next statement of . It looks like a function is being yield Several interruptions , Every interrupt passes yield Returns the current iteration value .

yield The benefits are obvious , Rewrite a function to a generator And you get the ability to iterate , Instead of saving the state of a class instance to calculate the next next() Value , Not only is the code concise , And the execution process is extremely clear .