J'ai essayé LeetCode tous les jours 13. Roman to Integer (Python, Go)

introduction

@Ishishow gère un site de mots anglais gratuit E-tan.

J'aimerais travailler quotidiennement sur letcode pour améliorer mes capacités de programmeur et donner ma propre façon de le résoudre.

Qu'est-ce que Leetcode

leetcode.com C'est la pratique de coder des interviews pour les développeurs de logiciels. Au total, plus de 1 500 questions de codage ont été affichées, et il semble que les mêmes questions soient souvent posées lors d'entretiens réels.

Introduction au langage Go + Algorithme Je vais le résoudre avec Golang et Python pour renforcer mon cerveau. (Python est faible mais expérimenté)

4e question (problème 13)

Roman to Integer

Contenu du problème (traduction japonaise)

: Les nombres romains sont représentés par sept symboles différents «I», «V», «X», «L», «C», «D» et «M». Valeur du symbole I 1 V 5 X 10 L 50 C 100 D 500 M 1000

Par exemple, les nombres romains`2`Yo`II`Écrit en, seuls les deux sont additionnés.`12`Est écrit`XII`est`X + II`.. C'est simple. nombre`27`Est écrit`XXVII`est`XX + V + II`。

Les nombres romains sont généralement écrits de gauche à droite, du maximum au minimum. Cependant, le chiffre 4 n'est pas`IIII`.. Au lieu de cela, le quatrième nombre est`IV`.. Est écrit. L'un est avant 5, alors soustrayez-le à 4. Le même principe est écrit`IX`Cela s'applique également au numéro 9. Il existe six exemples où la soustraction est utilisée:

- `I``V`(5) et`X`Il peut être placé devant (10) pour faire 4 et 9.
- `X``L`(50) et`C`Il peut être placé devant (100) pour faire 40 et 90.
- `C``D`(500) et`M`Vous pouvez le placer avant (1000) pour créer 400 et 900.

Étant donné un nombre romain, convertissez-le en entier.

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.

Conseils

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

Façon de penser

1.Faites une carte de hachage en référence à l'indice 2. Lisez la chaîne de caractères caractère par caractère, comparez le nombre correspondant au caractère avec le nombre correspondant au caractère suivant, ajoutez tel quel s'il est grand, et ajoutez la valeur obtenue en soustrayant ce caractère s'il est petit (code) Cela peut être plus rapide à voir)

Explication

Go définit la valeur initiale avec la fonction de carte. (J'ai utilisé make pour le problème de 1.Two Sum, mais cette fois la valeur initiale est incluse, donc la carte va bien)
Python est facile à manipuler des chaînes, je vais donc l'examiner plus tard, mais dans Go, je vais le convertir en tableau et regarder le caractère précédent.

--Code de réponse

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

La manipulation des chaînes est plus facile avec les tranches

Je l'écrirai aussi en Go!

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
}

Je regarde le numéro précédent avec une variable appelée carry. Puisque le nombre précédent est ajouté une fois, lorsque ce dernier nombre est plus grand, le nombre est soustrait deux fois.

J'ai également importé le package de chaînes car j'ai utilisé split pour créer les chaînes dans un tableau.

Temps d'exécution Go et Python

À partir de la gauche, RunTime, Memory, language.

キャプチャ.PNG