Force buckle |# 13 Roman numeral to integer

Title screenshot

First, use a dictionary to correspond Roman numerals to numbers

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

Then use the enumerate() function to traverse the string str to be studied, so that each element has a subscript index.

The enumerate() function is used to combine a traversable data object (such as list, tuple or string) into an index sequence, and list the data and data subscripts at the same time. It is generally used in the for loop.

Python enumerate() function - rookie tutorial

​​​​​​​

Idea: Roman numerals: if the value on the left is smaller than that on the right, the value is accumulated as a negative number. If the value on the left is larger or equal than that on the right, it is accumulated directly.

For example, "X I V", X=10, I = 1, V = 5.

                                X>I,    I<V,

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

For example, "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 + 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994

The last bit 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, elif is not used to judge, and else is used to cover other situations directly.

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"))

The enumerate() function can also be omitted

This method does not use in, so sum += romaNumberMap[s[i+1]] should be added separately after the loop

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"))

 

extend

During the interview, you may need to implement the enumerate() function yourself

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

Python 3 iterator and generator rookie tutorial

In Python, a function that uses yield is called a generator

Unlike ordinary functions, a generator is a function that returns an iterator and can only be used for iterative operations. It is easier to understand that a generator is an iterator.

In the process of calling the generator to run, the function will pause and save all the current running information every time it encounters yield, return the value of yield, and continue to run from the current position the next time it executes the next() method.

Call a generator function and return an iterator object.

See Python yield usage analysis | rookie tutorial

Function of yield: turn a function into a generator. The function with yield is no longer an ordinary function. The Python interpreter will treat it as a generator. When calling function f(x), it will not execute function f, but return an iterable object. During the execution of the for loop, the code inside the fab function will be executed every time the loop is executed. When the F function is executed to yield b, it will return an iteration value. In the next iteration, the code will continue to execute from the next statement of yield xxx, and the local variables of the function look exactly the same as before the execution was interrupted last time, so the function will continue to execute until yield is encountered again.

A function with yield is a generator, which is different from ordinary functions. Generating a generator looks like a function call, but it will not execute any function code until it calls next() (next() will be called automatically in the for loop). Although the execution process is still executed according to the process of the function, every time a yield statement is executed, it will be interrupted and return an iteration value. The next execution will continue from the next yield statement. It looks like a function is interrupted several times by yield during normal execution, and each interrupt will return the current iteration value through yield.

The advantage of yield is obvious. Rewriting a function into a generator can obtain the iterative ability. Compared with using the instance of the class to save the state to calculate the value of the next(), the code is not only concise, but also the execution process is extremely clear.