Roman to Integer
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
- sstring
- un número romano válido en letras mayúsculas
- Devuelveinteger
- el valor del numeral, de 1 a 3999
Restricciones
1 ≤ s.length ≤ 15scontiene solo los caracteresI,V,X,L,C,DyM.ses un numeral romano válido para un valor del 1 al 3999.
Ejemplos
- Entrada
- s = "XXVII"
- Salida
- 27
- Explicación
XXes 10 + 10,Ves 5 yIIes 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:
CDson 400,XLson 40 yIVson 4, lo que da 444.
- Entrada
- s = "MCDXCII"
- Salida
- 1492
- Explicación
Mes 1000,CDes 400,XCes 90 yIIes 2, así que el numeral es 1492. Los pares y los símbolos simples se pueden combinar libremente.
+22 pruebas ocultas al enviar
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.
Escribe el numeral como un valor por símbolo.
MCDXCIIse convierte en 1000, 100, 500, 10, 100, 1, 1. ¿Cuáles de esos valores deberían contar como negativos para que la suma dé 1492?Un símbolo se resta exactamente cuando el símbolo que le sigue vale más: la C en
CD, la X enXC. Todos los demás símbolos se suman, incluido un símbolo seguido de otro igual, como enII.Recorre la cadena una vez usando un índice. Compara el valor del símbolo actual con el del siguiente; resta el actual si es menor y súmalo en caso contrario. El último símbolo no tiene vecino, así que siempre se suma.
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 totalCompara 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
scon 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,
IIda 0 yXXda 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 primeroi+1con 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.
XCse 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
#sonchar(s).
Preguntas frecuentes4
¿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.
¿Esta solución comprueba que el numeral sea válido?
No. El problema garantiza un numeral válido, así que el código solo suma y resta. Si se le da una cadena no válida como IIII o VV, sigue devolviendo un número: 4 y 10. Para validar, convierte el resultado de nuevo a un numeral y compáralo con la entrada.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def romanToInt(s):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
s = "XXVII"
Esperado
27