I tried LeetCode every day 13. Roman to Integer (Python, Go)

Introduction

@Ishishow is running a free English word site E-tan.

I would like to work on letcode every day to improve my ability as a programmer and give my own way of solving it.

What is Leetcode

leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.

Introduction to Go language + algorithm I will solve it with Golang and Python to strengthen my brain. (Python is weak but experienced)

4th question (problem 13)

13. Roman to Integer

--Problem content (Japanese translation)

: Roman numerals are represented by seven different symbols I, V, X, L, C, D and M. Symbol value I 1 V 5 X 10 L 50 C 100 D 500 M 1000

For example, Roman numerals`2`Yo`II`Written in, only the two are added together.`12`Is written`XII`is`X + II`.. This is simple. number`27`Is written`XXVII`is`XX + V + II`。

Roman numerals are usually written from left to right, from maximum to minimum. However, the number 4 is not`IIII`.. Instead, the fourth number is`IV`.. Is written. One is before 5, so subtract it to 4. The same principle is written`IX`It also applies to number 9. There are six examples where subtraction is used:

- `I``V`(5) and`X`It can be placed in front of (10) to make 4 and 9.
- `X``L`(50) and`C`It can be placed in front of (100) to make 40 and 90.
- `C``D`(500) and`M`You can place it before (1000) to create 400 and 900.

Given a Roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3

Example 2:

Input: s = "IV"
Output: 4

Example 3:

Input: s = "IX"
Output: 9

Example 4:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Tips

I - 1
V - 5
X - 10
L - 50
C - 100
D - 500
M - 1000

**Rules:**
\* If I comes before V or X, subtract 1 eg: IV = 4 and IX = 9
\* If X comes before L or C, subtract 10 eg: XL = 40 and XC = 90
\* If C comes before D or M, subtract 100 eg: CD = 400 and CM = 900 

Way of thinking

1. Make a hash map with reference to the hint
2. Read the character string character by character, compare the number corresponding to the character with the number corresponding to the subsequent character, add it as it is if it is large, and add the value obtained by subtracting that character if it is small (code It may be faster to see)

Explanation

1. Go sets the initial value with the map function. (I used make for the problem of 1.Two Sum, but this time the initial value is included, so map is fine)

2. Python is easy to manipulate strings, so I'll look at it later, but in Go, I'll convert it to an array and look at the previous character.

--Answer code

class Solution(object):
    def romanToInt(self, s):
        roman = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        res, i = 0, 0
        for i in range(len(s)):
            curr, nxt = s[i], s[i+1:i+2]
            if nxt and roman[curr] < roman[nxt]:
                res -= roman[curr]
            else:
                res += roman[curr]
        return res

String manipulation is easier with slices

--I'll write it in Go too!

import "strings"

func romanToInt(s string) int {
    var number int = 0
    var carry int = 0
    hashT := map[string]int{
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
    }

    for _, v := range strings.Split(s, "") {
            if carry < hashT[v] {
                    number = number - (carry * 2) + hashT[v]
            } else {
                    number = number + hashT[v]
            }
            carry = hashT[v]
    }
    return number
}

I'm looking at the previous number with a variable called carry. Since the previous number is added once, when the latter number is larger, the number is subtracted twice.

I also imported the strings package because I used split to make the strings an array.

Go and Python execution time

From the left, RunTime, Memory, language.