Integer to Roman

Q: Wie hoch ist die Zeitkomplexität der Umwandlung einer Ganzzahl in eine römische Zahl?

O(1) . Die Eingabe ist höchstens 3999, daher prüft die Greedy-Schleife 13 Tabellenzeilen und hängt höchstens 15 Symbole an. Wenn größere Zahlen erlaubt wären und mit wiederholtem M geschrieben würden, würde die Laufzeit mit num / 1000 wachsen.

Q: Warum ist 3999 die größte zulässige Zahl?

M ist der größte Buchstabe, und kein Buchstabe darf viermal hintereinander vorkommen. Daher ist MMM das Maximum bei den Tausendern, und 3999 ist MMMCMXCIX . Größere Zahlen wurden mit zusätzlichen Zeichen geschrieben, zum Beispiel mit einem Strich über einem Buchstaben, um ihn mit 1000 zu multiplizieren.

MittelMathe und Simulation Greedy

+10

Römische Ziffern bestehen aus sieben Buchstaben: M 1000, D 500, C 100, L 50, X 10, V 5 und I 1. Die Buchstaben stehen in absteigender Reihenfolge und werden addiert, daher ist 7 gleich VII. Kein Buchstabe wird viermal hintereinander wiederholt: 4, 9, 40, 90, 400 und 900 werden als IV, IX, XL, XC, CD und CM geschrieben, wobei ein kleinerer Buchstabe vom nachfolgenden größeren subtrahiert wird. Nur bei diesen sechs Paaren steht ein kleinerer Buchstabe zuerst.

Gegeben ist eine ganze Zahl num. Gib ihre römische Zahlendarstellung zurück.

Funktion

intToRoman(num: integer) → string

numinteger: eine ganze Zahl von 1 bis 3999
Gibt zurückstring: die römische Zahl für num in Großbuchstaben

Einschränkungen

1 ≤ num ≤ 3999

Beispiele

Eingabe: num = 49
Ausgabe: "XLIX"
Erklärung: 49 ist 40 + 9, also lautet die Zahl XL gefolgt von IX: XLIX. IL ist nicht erlaubt, weil I nur bei IV und IX subtrahiert.

Eingabe: num = 2026
Ausgabe: "MMXXVI"
Erklärung: 2026 enthält weder die Ziffer 4 noch die Ziffer 9, daher ist kein Paar erforderlich, und die Buchstaben ergeben: 1000 + 1000 + 10 + 10 + 5 + 1 ist MMXXVI.

Eingabe: num = 944
Ausgabe: "CMXLIV"
Erklärung: 944 ist 900 + 40 + 4, und jeder Teil ist ein subtraktives Zahlenpaar: CM, XL und IV ergeben zusammen CMXLIV.

Weiterführende Frage

Kannst du bei einer Zeichenfolge prüfen, ob sie in dieser standardisierten Form eine römische Zahl ist, wobei XLIX akzeptiert und IIII, IL und VX abgelehnt werden?

Tipps

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

0 von 3 geöffnet

Lösung

Füge die sechs subtraktiven Paare als eigene Symbole zum Alphabet hinzu, und das Schreiben einer Zahl wird zum Wechseln: Nimm immer den größten Wert, der noch passt. Die Eingabe ist höchstens 3999, daher ist der Aufwand gering und fest begrenzt.

Schreibe es additiv und kürze dann die langen Formen.

Idee

Ignoriere die Paare zunächst: Schreibe so viele M, wie hineinpassen, dann D und so weiter bis hinunter zu I. Für 944 ergibt das DCCCCXXXXIIII. Diese additive Form unterscheidet sich von der Standardform nur dort, wo eine Ziffer 4 oder 9 ist, und diese Stellen entsprechen immer einem von sechs Strings mit einer Kurzform: DCCCC ist CM, CCCC ist CD, LXXXX ist XC, XXXX ist XL, VIIII ist IX und IIII ist IV.

Ersetze DCCCC vor CCCC, sonst wird aus 900 DCD; dasselbe gilt für die Zehner und Einer. Die additive Form hat höchstens 18 Buchstaben (3999), daher beträgt der Aufwand O(1), bezahlt mit einem zweiten Durchlauf und ein paar temporären Strings.

Algorithmus

Füge für jeden der sieben Buchstaben von M abwärts bis I den Buchstaben an, solange num mindestens seinen Wert hat, und ziehe den Wert jedes Mal ab.
Ersetze DCCCC durch CM, dann CCCC durch CD.
Ersetze LXXXX durch XC, dann XXXX durch XL.
Ersetze VIIII durch IX, dann IIII durch IV.
Gib die Zeichenfolge zurück.

def intToRoman(num):
    letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
    numeral = ""
    for value, letter in letters:
        while num >= value:
            numeral += letter
            num -= value
    # Each long form appears at most once; the longer one goes first.
    fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
             ("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
    for long_form, short_form in fixes:
        numeral = numeral.replace(long_form, short_form)
    return numeral

Gierig über die 13 Werte

Idee

Sortiere die sieben Buchstaben und sechs Paare nach ihrem Wert: M 1000, CM 900, D 500, CD 400, C 100, XC 90, L 50, XL 40, X 10, IX 9, V 5, IV 4, I 1. Es ist immer richtig, den größten passenden Wert zu nehmen. Jeder Wert einer niedrigeren Dezimalstelle ist kleiner als der kleinste Wert der darüberliegenden Stelle, deshalb beendet die Schleife ihre Arbeit eine Stelle, bevor sie die nächste erreicht. Innerhalb einer Stelle schreiben die Werte für 9, 5, 4 und 1 jede Ziffer auf die übliche Weise: 9 ist das 9-Symbol, 5 bis 8 sind das 5-Symbol plus bis zu drei 1-Symbole, 4 ist das 4-Symbol und 1 bis 3 sind 1-Symbole.

Für 3746 schreibt die Schleife MMM, D, CC, XL, V, I: MMMDCCXLVI. Die Tabelle hat 13 Zeilen und die Antwort höchstens 15 Buchstaben, daher beträgt der Aufwand O(1) in einem Durchlauf.

Algorithmus

Liste die 13 Werte mit ihren Symbolen auf, von 1000 bis 1, einschließlich der Paare.
Beginne mit einer leeren Zeichenfolge.
Füge für jede Zeile, solange num mindestens so groß wie der Wert ist, das Symbol hinzu und ziehe den Wert ab.
Gib die Zeichenfolge zurück, sobald alle Zeilen abgearbeitet sind.

def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    parts = []
    for value, symbol in zip(values, symbols):
        while num >= value:  # take the largest value that still fits
            parts.append(symbol)
            num -= value
    return "".join(parts)

Stolperfallen und Grenzfälle

D in der Tabelle vor CM zu setzen. 900 ergibt dann DCD.
Für jede Zeile if statt while zu verwenden. Für 3000 wird M dreimal benötigt; mit if ergibt sich MCMDCDCXCX.
Andere Paare zu erfinden. 99 ist XCIX, nicht IC, und 45 ist XLV, nicht VL.
In C einen zu kleinen Puffer zu verwenden. Die längste Antwort für 3888 hat 15 Buchstaben, daher benötigt sie 16 Bytes mit dem abschließenden Nullbyte; die additive Form benötigt 19.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der Umwandlung einer Ganzzahl in eine römische Zahl?

O(1). Die Eingabe ist höchstens 3999, daher prüft die Greedy-Schleife 13 Tabellenzeilen und hängt höchstens 15 Symbole an. Wenn größere Zahlen erlaubt wären und mit wiederholtem M geschrieben würden, würde die Laufzeit mit num / 1000 wachsen.

Kannst du eine ganze Zahl ohne eine Schleife über Werte in römische Zahlen umwandeln?

Ja. Lege für jede Dezimalstelle eine Tabelle mit den Zeichenfolgen für ihre Ziffern an, zum Beispiel "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM für die Hunderter. Schlage jede Ziffer von num nach und füge die Zeichenfolgen zusammen. Das ist ebenfalls O(1) bei 34 gespeicherten Zeichenfolgen.

Warum ist 3999 die größte zulässige Zahl?

M ist der größte Buchstabe, und kein Buchstabe darf viermal hintereinander vorkommen. Daher ist MMM das Maximum bei den Tausendern, und 3999 ist MMMCMXCIX. Größere Zahlen wurden mit zusätzlichen Zeichen geschrieben, zum Beispiel mit einem Strich über einem Buchstaben, um ihn mit 1000 zu multiplizieren.

def intToRoman(num):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

num = 49

Erwartete Ausgabe

"XLIX"