Roman to Integer

Q: ¿Por qué restas un símbolo que es más pequeño que el siguiente?

Así se construyen los seis pares sustractivos. En IV , IX , XL , XC , CD y CM , un símbolo menor va antes que uno mayor y el par vale el mayor menos el menor. Restar el primer símbolo y sumar el segundo da exactamente ese valor, y en ningún otro lugar de un numeral válido aparece un símbolo menor antes que uno mayor.

FácilMatemáticas y simulación Hashing

+10

Los números romanos usan siete símbolos: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 y M = 1000. Los símbolos se escriben de mayor a menor y se suman, excepto en seis pares sustractivos en los que aparece primero un símbolo menor y se resta del mayor: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 y CM = 900.

Se te da un número romano válido s. Devuelve el entero que representa.

Función

romanToInt(s: string) → integer

sstring: un número romano válido en letras mayúsculas
Devuelveinteger: el valor del numeral, de 1 a 3999

Restricciones

1 ≤ s.length ≤ 15
s contiene solo los caracteres I, V, X, L, C, D y M.
s es un numeral romano válido para un valor del 1 al 3999.

Ejemplos

Entrada: s = "XXVII"
Salida: 27
Explicación: XX es 10 + 10, V es 5 y II es 1 + 1, así que el total es 27. Ningún símbolo va seguido de uno más grande, así que se suman todos los símbolos.

Entrada: s = "CDXLIV"
Salida: 444
Explicación: El numeral consta de tres pares sustractivos seguidos: CD son 400, XL son 40 y IV son 4, lo que da 444.

Entrada: s = "MCDXCII"
Salida: 1492
Explicación: M es 1000, CD es 400, XC es 90 y II es 2, así que el numeral es 1492. Los pares y los símbolos simples se pueden combinar libremente.

Para ir más allá

¿Puedes escribir la operación inversa, convirtiendo un entero del 1 al 3999 en su número romano?

Pistas

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

0 de 3 abiertas

Solución

La mayor parte de un número es una suma simple, así que todo el problema consiste en detectar los seis pares sustractivos. Puedes buscarlos como tokens de dos letras o usar la única regla que abarca los seis: se resta un símbolo cuyo valor es menor que el de su vecino de la derecha. En cualquier caso, un solo recorrido de como máximo 15 caracteres da la respuesta.

Lee los pares sustractivos como tokens

Intuición

Piensa en el numeral como una fila de fichas. La mayoría de las fichas tienen un símbolo y seis tienen dos símbolos: IV, IX, XL, XC, CD y CM. Divide la cadena en esas fichas, suma sus valores y tendrás el número.

En cada posición, mira primero los dos caracteres siguientes. Si forman uno de los seis pares, suma el valor del par y avanza dos posiciones. De lo contrario, suma el valor del símbolo individual y avanza una posición. MCDXCII se divide en M, CD, XC, I, I: 1000 + 400 + 90 + 1 + 1 = 1492.

La comprobación del par debe hacerse primero. Si lees la X de XC por separado, sumas 10 y luego 100 y obtienes 110 en lugar de 90. La comprobación también es segura: en un numeral válido, un símbolo menor aparece justo antes de uno mayor únicamente dentro de uno de estos seis pares, así que todos los pares que encuentres son reales.

En cada paso se consumen uno o dos caracteres, así que el bucle se ejecuta como máximo 15 veces. Las dos tablas tienen un tamaño fijo, por lo que el espacio adicional es constante.

Algoritmo

Crea una tabla para los seis pares y otra para los siete símbolos individuales.
Empieza en el índice 0 con un total de 0.
Si los dos caracteres del índice forman un par, suma el valor del par y avanza el índice en 2.
De lo contrario, suma el valor del símbolo individual y avanza el índice en 1.
Cuando el índice supere el final, devuelve el total.

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

Compara cada símbolo con el siguiente

Intuición

Vuelve a mirar los seis pares. En todos, el primer símbolo vale menos que el segundo, y el valor del par es el segundo menos el primero. Así que puedes prescindir de la tabla de pares y usar una sola regla: si un símbolo vale menos que el símbolo que tiene a su derecha, réstalo; de lo contrario, súmalo. CM se convierte en -100 + 1000 = 900, el mismo valor que da la lectura de los tokens.

Recorre MCDXCII. A M le sigue una C más pequeña, así que suma 1000. A C le sigue una D más grande, así que resta 100: el total es 900. Suma D para llegar a 1400. A X le sigue una C más grande, así que resta 10: 1390. Suma C: 1490. A la primera I le sigue otra I igual, así que súmala: 1491. La última I no tiene ningún símbolo a su derecha, así que súmala también: 1492.

La comparación debe ser estrictamente menor que. Los símbolos iguales uno junto al otro siempre se suman, que es lo que hace que II sea 2 y XX sea 20. La regla es correcta por la misma razón que la lectura de los tokens: en un numeral válido, un símbolo más pequeño aparece justo antes de uno más grande solo como la primera mitad de un par sustractivo.

Examinas cada carácter una vez y mantienes un total acumulado, así que el tiempo es O(n) y el espacio adicional es O(1). Esta versión solo necesita los valores de los siete símbolos y una comparación por carácter.

Algoritmo

Almacena el valor de cada uno de los siete símbolos.
Recorre los índices de s con un total acumulado que empieza en 0.
Si el siguiente símbolo existe y vale más que el actual, resta el valor actual.
De lo contrario, suma el valor actual.
Devuelve el total después del bucle.

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

Errores comunes y casos límite

La regla es breve, así que los errores se deben a los casos límite.

Usar menor o igual en lugar de estrictamente menor. Entonces, II da 0 y XX da 0, porque se resta cada primer símbolo.
Leer el símbolo siguiente en el último carácter. s[i+1] no existe ahí; comprueba primero i+1 con respecto a la longitud y suma siempre el último símbolo.
En la versión con tokens, probar los símbolos individuales antes que los pares. XC se lee entonces como 10 + 100 = 110.
Detectar el par solo en su segundo símbolo. Si ya has sumado la I de IV, tienes que restarla dos veces: 1 + 5 - 2 × 1 = 4. Comparar con el símbolo siguiente evita esa corrección.
Olvidar que las cadenas de Lua y R empiezan en el índice 1, así que el último símbolo está en #s o nchar(s).

Preguntas frecuentes3

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

Ambos enfoques leen cada carácter una vez, por lo que el tiempo es O(n) para un numeral de n caracteres. El espacio adicional es O(1), porque las tablas de consulta tienen un tamaño fijo. Un numeral del 1 al 3999 tiene como máximo 15 caracteres, así que, en la práctica, el trabajo es mínimo.

¿Por qué restas un símbolo que es más pequeño que el siguiente?

Así se construyen los seis pares sustractivos. En IV, IX, XL, XC, CD y CM, un símbolo menor va antes que uno mayor y el par vale el mayor menos el menor. Restar el primer símbolo y sumar el segundo da exactamente ese valor, y en ningún otro lugar de un numeral válido aparece un símbolo menor antes que uno mayor.

¿Puedes convertir un número romano de derecha a izquierda?

Sí. Recorre desde el último símbolo hasta el primero y recuerda el valor del símbolo que leíste antes, el que está a la derecha. Si el símbolo actual vale menos que ese, réstalo; de lo contrario, súmalo. Es la misma regla que la versión de izquierda a derecha, vista desde el otro lado.

def romanToInt(s):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "XXVII"

Salida Esperada