Integer to Roman

Q: Qual è la complessità temporale della conversione da Integer a Roman?

O(1) . L’input è al massimo 3999, quindi il ciclo greedy controlla 13 righe della tabella e aggiunge al massimo 15 simboli. Se fossero ammessi numeri più grandi e venissero scritti con M ripetute, il tempo crescerebbe con num / 1000 .

Q: Perché 3999 è il numero più grande consentito?

M è la lettera di valore più alto e nessuna lettera può comparire quattro volte di seguito, quindi MMM è il massimo per le migliaia e 3999 è MMMCMXCIX . I numeri più grandi venivano scritti con segni aggiuntivi, come una barra sopra una lettera per moltiplicarla per 1000.

MedioMatematica e simulazione Greedy

+10

I numeri romani hanno sette lettere: M 1000, D 500, C 100, L 50, X 10, V 5 e I 1. Le lettere vanno dalla più grande alla più piccola e si sommano, quindi 7 è VII. Nessuna lettera si ripete quattro volte di seguito: 4, 9, 40, 90, 400 e 900 si scrivono IV, IX, XL, XC, CD e CM, una lettera più piccola sottratta a quella più grande che la segue. Solo queste sei coppie mettono prima una lettera più piccola.

Dato un intero num, restituisci il suo numero romano.

Funzione

intToRoman(num: integer) → string

numinteger: un numero intero da 1 a 3999
Restituiscestring: il numero romano di num in lettere maiuscole

Vincoli

1 ≤ num ≤ 3999

Esempi

Input: num = 49
Output: "XLIX"
Spiegazione: 49 è 40 + 9, quindi il numero è XL seguito da IX: XLIX. IL non è consentito, perché I si sottrae solo in IV e IX.

Input: num = 2026
Output: "MMXXVI"
Spiegazione: Il 2026 non contiene le cifre 4 o 9, quindi non serve alcuna coppia e le lettere si sommano: 1000 + 1000 + 10 + 10 + 5 + 1 è MMXXVI.

Input: num = 944
Output: "CMXLIV"
Spiegazione: 944 è 900 + 40 + 4 e ogni parte è una coppia sottrattiva: CM, XL e IV si uniscono in CMXLIV.

Per approfondire

Data una stringa, puoi verificare che sia un numero romano in questa forma standard, accettando XLIX e rifiutando IIII, IL e VX?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Aggiungi le sei coppie sottrattive all’alfabeto come simboli autonomi, e scrivere un numero diventa come fare il resto: scegli sempre il valore più grande che ci sta ancora. L’input è al massimo 3999, quindi il lavoro è una piccola quantità fissa.

Scrivilo in forma additiva, poi accorcia le forme lunghe

Intuizione

Per prima cosa ignora le coppie: scrivi tutti gli M che ci stanno, poi D e così via fino a I. Per 944 si ottiene DCCCCXXXXIIII. Questa forma additiva differisce da quella standard solo quando una cifra è 4 o 9, e in quei punti si trova sempre una delle sei stringhe con una forma abbreviata: DCCCC è CM, CCCC è CD, LXXXX è XC, XXXX è XL, VIIII è IX e IIII è IV.

Sostituisci DCCCC prima di CCCC, altrimenti 900 diventa DCD; lo stesso vale per le decine e le unità. La forma additiva ha al massimo 18 lettere (3999), quindi il lavoro è O(1), a costo di un secondo passaggio e di alcune stringhe temporanee.

Algoritmo

Per ciascuna delle sette lettere, da M a I, aggiungila finché num è almeno pari al suo valore e sottrai il valore ogni volta.
Sostituisci DCCCC con CM, poi CCCC con CD.
Sostituisci LXXXX con XC, poi XXXX con XL.
Sostituisci VIIII con IX, poi IIII con IV.
Restituisci la stringa.

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

Greedy sui 13 valori

Intuizione

Ordina le sette lettere e le sei coppie per valore: 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. Scegliere il valore più grande che ci sta è sempre corretto. Ogni valore di una posizione decimale inferiore è minore del valore più piccolo della posizione superiore, quindi il ciclo termina una posizione prima di passare a quella successiva. All’interno di una posizione, i valori per 9, 5, 4 e 1 rappresentano ogni cifra nel modo standard: 9 è il simbolo del 9, da 5 a 8 sono il simbolo del 5 più fino a tre simboli dell’1, 4 è il simbolo del 4 e da 1 a 3 sono simboli dell’1.

Per 3746 il ciclo scrive MMM, D, CC, XL, V, I: MMMDCCXLVI. La tabella ha 13 righe e la risposta al massimo 15 lettere, quindi il lavoro è O(1), in un solo passaggio.

Algoritmo

Elenca i 13 valori con i relativi simboli, da 1000 a 1, comprese le coppie.
Inizia con una stringa vuota.
Per ogni riga, finché num è almeno pari al valore, aggiungi il simbolo e sottrai il valore.
Restituisci la stringa quando hai terminato tutte le righe.

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)

Trappole e casi limite

Mettere D prima di CM nella tabella. 900 diventa quindi DCD.
Usare if invece di while per ogni riga. 3000 ha bisogno di M tre volte; con if diventa MCMDCDCXCX.
Inventare altre coppie. 99 è XCIX, non IC, e 45 è XLV, non VL.
In C, usare un buffer troppo piccolo. La risposta più lunga, per 3888, ha 15 lettere, quindi servono 16 byte con lo zero terminatore; la forma additiva ne richiede 19.

Domande frequenti3

Qual è la complessità temporale della conversione da Integer a Roman?

O(1). L’input è al massimo 3999, quindi il ciclo greedy controlla 13 righe della tabella e aggiunge al massimo 15 simboli. Se fossero ammessi numeri più grandi e venissero scritti con M ripetute, il tempo crescerebbe con num / 1000.

Riesci a convertire un intero in numeri romani senza un ciclo sui valori?

Sì. Tieni una tabella per ogni posizione decimale con le stringhe delle sue cifre, ad esempio "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM per le centinaia. Cerca ogni cifra di num e unisci le stringhe. È anche O(1), con 34 stringhe memorizzate.

Perché 3999 è il numero più grande consentito?

M è la lettera di valore più alto e nessuna lettera può comparire quattro volte di seguito, quindi MMM è il massimo per le migliaia e 3999 è MMMCMXCIX. I numeri più grandi venivano scritti con segni aggiuntivi, come una barra sopra una lettera per moltiplicarla per 1000.

def intToRoman(num):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

num = 49

Output atteso

"XLIX"