Integer to Roman

Q: ¿Cuál es la complejidad temporal de Integer to Roman?

O(1) . La entrada es como máximo 3999, así que el bucle voraz comprueba 13 filas de la tabla y añade como máximo 15 símbolos. Si se permitieran números más grandes y se escribieran con M repetidas, el tiempo aumentaría en función de num / 1000 .

Q: ¿Por qué 3999 es el número más grande permitido?

M es la letra de mayor valor y ninguna letra puede aparecer cuatro veces seguidas, por lo que MMM es el máximo en los millares, y 3999 es MMMCMXCIX . Los números mayores se escribían con marcas adicionales, como una barra sobre una letra para multiplicar su valor por 1000.

MedioMatemáticas y simulación Voraz

+10

Los números romanos tienen siete letras: M 1000, D 500, C 100, L 50, X 10, V 5 y I 1. Las letras van de mayor a menor y se suman, así que 7 es VII. Ninguna letra se repite cuatro veces seguidas: 4, 9, 40, 90, 400 y 900 se escriben IV, IX, XL, XC, CD y CM; una letra menor se resta de la mayor que va después. Solo estos seis pares colocan primero una letra menor.

Dado un entero num, devuelve su número romano.

Función

intToRoman(num: integer) → string

numinteger: un número entero del 1 al 3999
Devuelvestring: el número romano de num en mayúsculas

Restricciones

1 ≤ num ≤ 3999

Ejemplos

Entrada: num = 49
Salida: "XLIX"
Explicación: 49 es 40 + 9, así que el numeral es XL después IX: XLIX. IL no está permitido, porque I solo resta en IV y IX.

Entrada: num = 2026
Salida: "MMXXVI"
Explicación: 2026 no tiene ningún dígito 4 ni 9, así que no se necesita ningún par y las letras se suman: 1000 + 1000 + 10 + 10 + 5 + 1 es MMXXVI.

Entrada: num = 944
Salida: "CMXLIV"
Explicación: 944 es 900 + 40 + 4, y cada parte es un par sustractivo: CM, XL y IV se unen para formar CMXLIV.

Para ir más allá

Dada una cadena, ¿puedes comprobar que sea un número romano en esta forma estándar, aceptando XLIX y rechazando IIII, IL y VX?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Añade los seis pares sustractivos al alfabeto como símbolos propios, y escribir un numeral se convierte en dar cambio: toma siempre el valor más grande que todavía quepa. La entrada es como máximo 3999, así que el trabajo es una cantidad pequeña y fija.

Escríbelo de forma aditiva y después acorta las formas largas

Intuición

Ignora los pares al principio: escribe tantos M como quepan, después D, y así sucesivamente hasta llegar a I. Para 944, eso da DCCCCXXXXIIII. Esta forma aditiva solo difiere de la estándar cuando un dígito es 4 o 9, y esos casos siempre corresponden a una de seis cadenas con una forma abreviada: DCCCC es CM, CCCC es CD, LXXXX es XC, XXXX es XL, VIIII es IX e IIII es IV.

Reemplaza DCCCC antes que CCCC, o 900 se convierte en DCD; lo mismo ocurre con las decenas y las unidades. La forma aditiva tiene como máximo 18 letras (3999), así que el trabajo es O(1), a cambio de una segunda pasada y unas pocas cadenas temporales.

Algoritmo

Para cada una de las siete letras desde M hasta I, añádela mientras num sea al menos igual a su valor y resta el valor cada vez.
Reemplaza DCCCC por CM, después CCCC por CD.
Reemplaza LXXXX por XC, después XXXX por XL.
Reemplaza VIIII por IX, después IIII por IV.
Devuelve la cadena.

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

Voraz con los 13 valores

Intuición

Ordena las siete letras y los seis pares por valor: 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. Elegir siempre el valor más grande que quepa es lo correcto. Todos los valores de una posición decimal inferior son menores que el valor más pequeño de la posición superior, así que el bucle termina una posición antes de llegar a la siguiente. Dentro de una posición, los valores para 9, 5, 4 y 1 escriben cada dígito de la forma estándar: 9 es el símbolo del 9, de 5 a 8 son el símbolo del 5 más hasta tres símbolos del 1, 4 es el símbolo del 4, y de 1 a 3 son símbolos del 1.

Para 3746, el bucle escribe MMM, D, CC, XL, V, I: MMMDCCXLVI. La tabla tiene 13 filas y la respuesta, como máximo, 15 letras, así que el trabajo es O(1), en una sola pasada.

Algoritmo

Enumera los 13 valores con sus símbolos, de 1000 a 1, incluidos los pares.
Empieza con una cadena vacía.
Para cada fila, mientras num sea al menos igual al valor, añade el símbolo y resta el valor.
Devuelve la cadena cuando se hayan completado todas las filas.

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)

Errores comunes y casos límite

Colocar D antes de CM en la tabla. Así, 900 da DCD.
Usar if en lugar de while para cada fila. 3000 necesita M tres veces; con if, da MCMDCDCXCX.
Inventar otros pares. 99 es XCIX, no IC, y 45 es XLV, no VL.
En C, usar un búfer demasiado pequeño. La respuesta más larga, para 3888, tiene 15 letras, así que necesita 16 bytes con el cero terminador; la forma aditiva necesita 19.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Integer to Roman?

O(1). La entrada es como máximo 3999, así que el bucle voraz comprueba 13 filas de la tabla y añade como máximo 15 símbolos. Si se permitieran números más grandes y se escribieran con M repetidas, el tiempo aumentaría en función de num / 1000.

¿Puedes convertir un entero a números romanos sin recorrer los valores con un bucle?

Sí. Mantén una tabla por cada posición decimal con las cadenas de sus dígitos, como "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM para las centenas. Busca cada dígito de num y une las cadenas. También es O(1), con 34 cadenas almacenadas.

¿Por qué 3999 es el número más grande permitido?

M es la letra de mayor valor y ninguna letra puede aparecer cuatro veces seguidas, por lo que MMM es el máximo en los millares, y 3999 es MMMCMXCIX. Los números mayores se escribían con marcas adicionales, como una barra sobre una letra para multiplicar su valor por 1000.

def intToRoman(num):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

num = 49

Salida Esperada

"XLIX"