Roman to Integer

Q: Warum ziehst du ein Symbol ab, das kleiner als das nächste ist?

So werden die sechs subtraktiven Paare gebildet. Bei IV , IX , XL , XC , CD und CM steht ein kleineres Symbol vor einem größeren, und das Paar ist so viel wert wie das größere minus das kleinere. Zieht man das erste Symbol ab und addiert das zweite, erhält man genau diesen Wert. An keiner anderen Stelle in einer gültigen Zahl steht ein kleineres Symbol vor einem größeren.

LeichtMathe und Simulation Hashing

+10

Römische Zahlen verwenden sieben Symbole: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 und M = 1000. Die Symbole werden von der größten zur kleinsten Zahl geschrieben und addiert, außer bei sechs subtraktiven Paaren, bei denen ein kleineres Symbol zuerst steht und von dem größeren abgezogen wird: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 und CM = 900.

Du erhältst eine gültige römische Zahl s. Gib die ganze Zahl zurück, für die sie steht.

Funktion

romanToInt(s: string) → integer

sstring: eine gültige römische Zahl in Großbuchstaben
Gibt zurückinteger: der Wert der Zahl, von 1 bis 3999

Einschränkungen

1 ≤ s.length ≤ 15
s enthält nur die Zeichen I, V, X, L, C, D und M.
s ist eine gültige römische Zahl für einen Wert von 1 bis 3999.

Beispiele

Eingabe: s = "XXVII"
Ausgabe: 27
Erklärung: XX ist 10 + 10, V ist 5 und II ist 1 + 1, also beträgt die Summe 27. Auf kein Symbol folgt ein größeres, daher wird jedes Symbol addiert.

Eingabe: s = "CDXLIV"
Ausgabe: 444
Erklärung: Die Zahl besteht aus drei aufeinanderfolgenden subtraktiven Paaren: CD ist 400, XL ist 40 und IV ist 4, was 444 ergibt.

Eingabe: s = "MCDXCII"
Ausgabe: 1492
Erklärung: M ist 1000, CD ist 400, XC ist 90 und II ist 2, also lautet die Zahl 1492. Paare und einzelne Symbole lassen sich beliebig kombinieren.

+22 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du die Umkehrung schreiben, die eine ganze Zahl von 1 bis 3999 in ihre römische Zahl umwandelt?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Der größte Teil einer römischen Zahl ist eine einfache Summe, daher besteht das ganze Problem darin, die sechs subtraktiven Paare zu erkennen. Du kannst sie als Zwei-Zeichen-Tokens nachschlagen oder die eine Regel verwenden, die für alle sechs gilt: Ein Symbol mit einem geringeren Wert als sein rechter Nachbar wird abgezogen. In beiden Fällen liefert ein einziger Durchlauf über höchstens 15 Zeichen die Antwort.

Subtraktive Paare als Token lesen

Idee

Stell dir die Zahl als eine Reihe von Zeichen vor. Die meisten Zeichen bestehen aus einem Symbol, und sechs bestehen aus zwei Symbolen: IV, IX, XL, XC, CD und CM. Teile die Zeichenfolge in diese Zeichen auf, addiere ihre Werte, und du hast die Zahl.

Betrachte an jeder Position zuerst die nächsten beiden Zeichen. Wenn sie eines der sechs Paare bilden, addiere den Wert des Paars und überspringe beide. Andernfalls addiere den Wert des einzelnen Symbols und überspringe eines. MCDXCII wird in M, CD, XC, I, I aufgeteilt: 1000 + 400 + 90 + 1 + 1 = 1492.

Die Prüfung auf ein Paar muss zuerst erfolgen. Wenn du das X von XC einzeln liest, addierst du 10 und dann 100 und erhältst 110 statt 90. Die Prüfung ist außerdem sicher: In einer gültigen Zahl steht ein kleineres Symbol nur innerhalb eines dieser sechs Paare direkt vor einem größeren, daher ist jedes gefundene Paar tatsächlich eines.

Jeder Schritt verarbeitet ein oder zwei Zeichen, daher läuft die Schleife höchstens 15-mal. Die beiden Tabellen haben eine feste Größe, daher ist der zusätzliche Speicherbedarf konstant.

Algorithmus

Erstelle eine Tabelle für die sechs Paare und eine für die sieben einzelnen Symbole.
Beginne bei Index 0 mit einer Summe von 0.
Wenn die beiden Zeichen am Index ein Paar bilden, addiere den Wert des Paares und erhöhe den Index um 2.
Andernfalls addiere den Wert des einzelnen Symbols und erhöhe den Index um 1.
Wenn der Index das Ende überschreitet, gib die Summe zurück.

def romanToInt(s):
    pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
    singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    i = 0
    while i < len(s):
        two = s[i:i + 2]
        if two in pairs:
            total += pairs[two]
            i += 2
        else:
            total += singles[s[i]]
            i += 1
    return total

Vergleiche jedes Symbol mit dem nächsten

Idee

Sieh dir die sechs Paare noch einmal an. Bei jedem ist das erste Symbol weniger wert als das zweite, und der Wert des Paares entspricht dem zweiten minus dem ersten. Du kannst also die Paartabelle weglassen und eine Regel verwenden: Wenn ein Symbol weniger wert ist als das Symbol rechts davon, ziehe es ab; andernfalls addiere es. CM wird zu -100 + 1000 = 900, demselben Wert, den das Auslesen der Token ergibt.

Gehe MCDXCII durch. Auf M folgt ein kleineres C, also addiere 1000. Auf C folgt ein größeres D, also ziehe 100 ab: Die Summe beträgt 900. Addiere D, um auf 1400 zu kommen. Auf X folgt ein größeres C, also ziehe 10 ab: 1390. Addiere C: 1490. Auf das erste I folgt ein gleiches I, also addiere es: 1491. Das letzte I hat keinen Nachbarn, also addiere es ebenfalls: 1492.

Der Vergleich muss strikt kleiner sein. Gleiche Nachbarn werden immer addiert, wodurch II den Wert 2 und XX den Wert 20 erhält. Die Regel ist aus demselben Grund korrekt wie das Auslesen der Token: In einer gültigen Zahl steht ein kleineres Symbol unmittelbar vor einem größeren nur als erste Hälfte eines Subtraktionspaares.

Du betrachtest jedes Zeichen einmal und führst eine laufende Summe, daher beträgt die Laufzeit O(n) und der zusätzliche Speicherbedarf O(1). Diese Version benötigt nur die sieben Symbolwerte und einen Vergleich pro Zeichen.

Algorithmus

Speichere den Wert jedes der sieben Symbole.
Durchlaufe die Indizes von s mit einer laufenden Summe, die bei 0 beginnt.
Wenn das nächste Symbol existiert und mehr wert ist als das aktuelle, ziehe den aktuellen Wert ab.
Andernfalls addiere den aktuellen Wert.
Gib nach der Schleife die Summe zurück.

def romanToInt(s):
    values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i in range(len(s)):
        value = values[s[i]]
        # A symbol worth less than the one after it is subtracted, like the I in IV.
        if i + 1 < len(s) and value < values[s[i + 1]]:
            total -= value
        else:
            total += value
    return total

Stolperfallen und Grenzfälle

Die Regel ist kurz, daher betreffen die Fehler ihre Grenzfälle.

Weniger als oder gleich statt strikt weniger als verwenden. Dann ergibt II 0 und XX 0, weil jeweils das erste Symbol abgezogen wird.
Beim letzten Zeichen das nächste Symbol lesen. s[i+1] existiert dort nicht; prüfe zuerst i+1 anhand der Länge und addiere immer das letzte Symbol.
In der Token-Variante einzelne Symbole vor Paaren ausprobieren. XC wird dann als 10 + 100 = 110 gelesen.
Das Paar erst an seinem zweiten Symbol erkennen. Wenn du das I von IV bereits addiert hast, musst du es zweimal abziehen: 1 + 5 - 2 × 1 = 4. Der Vergleich mit dem nächsten Symbol vermeidet diese Korrektur.
Vergessen, dass Lua- und R-Zeichenketten bei Index 1 beginnen, sodass das letzte Symbol an Position #s oder nchar(s) steht.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität der Umwandlung von römischen Zahlen in Ganzzahlen?

Beide Ansätze lesen jedes Zeichen einmal, daher beträgt die Laufzeit für eine Zahl mit n Zeichen O(n). Der zusätzliche Speicherbedarf beträgt O(1), da die Nachschlagetabellen eine feste Größe haben. Eine Zahl von 1 bis 3999 hat höchstens 15 Zeichen, daher ist der Aufwand in der Praxis sehr gering.

Warum ziehst du ein Symbol ab, das kleiner als das nächste ist?

So werden die sechs subtraktiven Paare gebildet. Bei IV, IX, XL, XC, CD und CM steht ein kleineres Symbol vor einem größeren, und das Paar ist so viel wert wie das größere minus das kleinere. Zieht man das erste Symbol ab und addiert das zweite, erhält man genau diesen Wert. An keiner anderen Stelle in einer gültigen Zahl steht ein kleineres Symbol vor einem größeren.

Kannst du eine römische Zahl von rechts nach links umwandeln?

Ja. Gehe vom letzten Symbol zum ersten und merke dir den Wert des Symbols, das du zuvor gelesen hast, also des Symbols rechts davon. Wenn das aktuelle Symbol weniger wert ist als dieses, ziehe es ab; andernfalls addiere es. Es ist dieselbe Regel wie bei der Version von links nach rechts, nur von der anderen Seite betrachtet.

Prüft diese Lösung, ob die Zahl gültig ist?

Nein. Die Aufgabenstellung garantiert eine gültige Zahl, daher addiert und subtrahiert der Code nur. Bei einer ungültigen Zeichenfolge wie IIII oder VV gibt er trotzdem eine Zahl zurück: 4 und 10. Um die Eingabe zu validieren, wandle das Ergebnis zurück in eine Zahl und vergleiche es mit der Eingabe.

Python

def romanToInt(s):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "XXVII"

Erwartet