Integer to Roman

Q: Qual é a complexidade de tempo da conversão de inteiro para romano?

O(1) . A entrada é no máximo 3999, então o loop guloso verifica 13 linhas da tabela e acrescenta no máximo 15 símbolos. Se números maiores fossem permitidos e escritos com M repetido, o tempo cresceria proporcionalmente a num / 1000 .

Q: Por que 3999 é o maior número permitido?

M é a maior letra, e nenhuma letra pode aparecer quatro vezes seguidas, então MMM é o limite para os milhares, e 3999 é MMMCMXCIX . Números maiores eram escritos com marcas adicionais, como uma barra sobre uma letra para multiplicá-la por 1000.

MédioMatemática e simulação Guloso

+10

Os numerais romanos têm sete letras: M 1000, D 500, C 100, L 50, X 10, V 5 e I 1. As letras vão da maior para a menor e seus valores são somados, então 7 é VII. Nenhuma letra se repete quatro vezes seguidas: 4, 9, 40, 90, 400 e 900 são escritos como IV, IX, XL, XC, CD e CM; nesses casos, uma letra menor é subtraída da maior que vem depois dela. Somente esses seis pares colocam uma letra menor primeiro.

Dado um inteiro num, retorne seu numeral romano.

Função

intToRoman(num: integer) → string

numinteger: um número inteiro de 1 a 3999
Retornastring: o numeral romano de num em letras maiúsculas

Restrições

1 ≤ num ≤ 3999

Exemplos

Entrada: num = 49
Saída: "XLIX"
Explicação: 49 é 40 + 9, então o numeral é XL seguido de IX: XLIX. IL não é permitido, porque I só subtrai em IV e IX.

Entrada: num = 2026
Saída: "MMXXVI"
Explicação: 2026 não tem os dígitos 4 nem 9, então nenhum par é necessário e as letras somam: 1000 + 1000 + 10 + 10 + 5 + 1 é MMXXVI.

Entrada: num = 944
Saída: "CMXLIV"
Explicação: 944 é 900 + 40 + 4, e cada parte é um par subtrativo: CM, XL e IV se juntam para formar CMXLIV.

Para ir além

Dada uma string, você consegue verificar se ela é um numeral romano nessa forma padrão, aceitando XLIX e rejeitando IIII, IL e VX?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Adicione os seis pares subtrativos ao alfabeto como símbolos próprios, e escrever um numeral se torna fazer troco: sempre pegue o maior valor que ainda couber. A entrada é de no máximo 3999, então o trabalho é uma quantidade pequena e fixa.

Escreva de forma aditiva e, em seguida, abrevie as formas longas

Intuição

Ignore os pares no início: escreva tantos M quanto couberem, depois D e assim por diante até I. Para 944, isso resulta em DCCCCXXXXIIII. Essa forma aditiva difere da forma padrão apenas onde um dígito é 4 ou 9, e esses lugares são sempre uma das seis sequências com uma forma abreviada: DCCCC é CM, CCCC é CD, LXXXX é XC, XXXX é XL, VIIII é IX e IIII é IV.

Substitua DCCCC antes de CCCC, ou 900 se transforma em DCD; o mesmo vale para as dezenas e as unidades. A forma aditiva tem no máximo 18 letras (3999), então o trabalho é O(1), pago com uma segunda passagem e algumas strings temporárias.

Algoritmo

Para cada uma das sete letras, de M até I, acrescente-a enquanto num for pelo menos igual ao seu valor e subtraia o valor a cada vez.
Substitua DCCCC por CM e, em seguida, CCCC por CD.
Substitua LXXXX por XC e, em seguida, XXXX por XL.
Substitua VIIII por IX e, em seguida, IIII por IV.
Retorne a string.

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

Ganancioso sobre os 13 valores

Intuição

Ordene as sete letras e os 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. Escolher o maior valor que cabe é sempre correto. Todo valor de uma casa decimal inferior é menor que o menor valor da casa acima, então o loop termina uma casa antes de alcançar a próxima. Dentro de uma casa, os valores 9, 5, 4 e 1 representam cada algarismo da maneira padrão: 9 é o símbolo de 9, de 5 a 8 são o símbolo de 5 mais até três símbolos de 1, 4 é o símbolo de 4, e de 1 a 3 são símbolos de 1.

Para 3746, o loop escreve MMM, D, CC, XL, V, I: MMMDCCXLVI. A tabela tem 13 linhas e a resposta tem no máximo 15 letras, então o trabalho é O(1), em uma única passagem.

Algoritmo

Liste os 13 valores com seus símbolos, de 1000 até 1, incluindo os pares.
Comece com uma string vazia.
Para cada linha, enquanto num for maior ou igual ao valor, acrescente o símbolo e subtraia o valor.
Retorne a string quando todas as linhas estiverem concluídas.

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)

Armadilhas e casos extremos

Colocar D antes de CM na tabela. 900 então resulta em DCD.
Usar if em vez de while para cada linha. 3000 precisa de M três vezes; com if, resulta em MCMDCDCXCX.
Inventar outros pares. 99 é XCIX, não IC, e 45 é XLV, não VL.
Em C, um buffer pequeno demais. A resposta mais longa, para 3888, tem 15 letras, então precisa de 16 bytes com o zero terminador; a forma aditiva precisa de 19.

Perguntas frequentes3

Qual é a complexidade de tempo da conversão de inteiro para romano?

O(1). A entrada é no máximo 3999, então o loop guloso verifica 13 linhas da tabela e acrescenta no máximo 15 símbolos. Se números maiores fossem permitidos e escritos com M repetido, o tempo cresceria proporcionalmente a num / 1000.

Você consegue converter um número inteiro em algarismos romanos sem percorrer os valores em um loop?

Sim. Mantenha uma tabela para cada casa decimal com as strings de seus dígitos, como "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM para as centenas. Consulte cada dígito de num e junte as strings. Isso também é O(1), com 34 strings armazenadas.

Por que 3999 é o maior número permitido?

M é a maior letra, e nenhuma letra pode aparecer quatro vezes seguidas, então MMM é o limite para os milhares, e 3999 é MMMCMXCIX. Números maiores eram escritos com marcas adicionais, como uma barra sobre uma letra para multiplicá-la por 1000.

def intToRoman(num):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

num = 49

Saída Esperada

"XLIX"