Ich habe jeden Tag 13 LeetCode ausprobiert. Roman to Integer (Python, Go)

Einführung

@Ishishow betreibt eine kostenlose englische Word-Site E-tan.

Ich möchte jeden Tag an Letcode arbeiten, um meine Fähigkeiten als Programmierer zu verbessern und meine eigene Art der Lösung zu finden.

Was ist Leetcode?

leetcode.com Dies ist die Praxis des Codierens von Interviews für Softwareentwickler. Insgesamt wurden mehr als 1.500 Codierungsfragen gestellt, und es scheint, dass in tatsächlichen Interviews häufig dieselben Fragen gestellt werden.

Einführung in Go Sprache + Algorithmus Ich werde es mit Golang und Python lösen, um mein Gehirn zu stärken. (Python ist schwach, aber erfahren)

4. Frage (Problem 13)

Roman to Integer

--Probleminhalt (japanische Übersetzung)

: Römische Zahlen werden durch sieben verschiedene Symbole "I", "V", "X", "L", "C", "D" und "M" dargestellt. Symbolwert I 1 V 5 X 10 L 50 C 100 D 500 M 1000

Zum Beispiel römische Zahlen`2`Yo`II`Eingeschrieben werden nur die beiden addiert.`12`Ist geschrieben`XII`ist`X + II`.. Das ist einfach. Nummer`27`Ist geschrieben`XXVII`ist`XX + V + II`。

Römische Zahlen werden normalerweise von links nach rechts geschrieben, von maximal bis minimal. Die Nummer 4 ist jedoch nicht`IIII`.. Stattdessen ist die vierte Zahl`IV`.. Ist geschrieben. Eins ist vor 5, also subtrahiere es zu 4. Das gleiche Prinzip ist geschrieben`IX`Dies gilt auch für Nummer 9. Es gibt sechs Beispiele, bei denen Subtraktion verwendet wird:

- `I``V`(5) und`X`Es kann vor (10) platziert werden, um 4 und 9 zu machen.
- `X``L`(50) und`C`Es kann vor (100) platziert werden, um 40 und 90 zu machen.
- `C``D`(500) und`M`Sie können es vor (1000) platzieren, um 400 und 900 zu erstellen.

Konvertieren Sie eine römische Zahl in eine ganze Zahl.

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.

Tipps

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

Denkweise

Erstellen Sie eine Hash-Map mit Bezug auf den Hinweis
Lesen Sie die Zeichenfolge zeichenweise, vergleichen Sie die dem Zeichen entsprechende Zahl mit der Zahl des nachfolgenden Zeichens, addieren Sie sie so, wie sie ist, wenn sie groß ist, und addieren Sie den Wert, der durch Subtrahieren dieser Zeichnung erhalten wird, wenn sie klein ist (Code). Es kann schneller zu sehen sein)

Erläuterung

Go setzt den Anfangswert mit der Kartenfunktion. (Ich habe make für das Problem von 1.Two Sum verwendet, aber diesmal ist der Anfangswert enthalten, sodass die Karte in Ordnung ist.)
Python ist einfach zu manipulieren, also werde ich es mir später ansehen, aber in Go werde ich es in ein Array konvertieren und das vorherige Zeichen betrachten.

--Antwortcode

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

Die String-Manipulation ist mit Slices einfacher

Ich werde es auch in Go schreiben!

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
}

Ich betrachte die vorherige Nummer mit einer Variablen namens Carry. Da die vorherige Zahl einmal addiert wird und die letztere Zahl größer ist, wird die Zahl zweimal subtrahiert.

Ich habe auch das Strings-Paket importiert, weil ich Split verwendet habe, um die Strings in ein Array zu verwandeln.

Go und Python-Ausführungszeit

Von links RunTime, Speicher, Sprache.

キャプチャ.PNG