Roman to Integer

Q: Por que você subtrai um símbolo que é menor que o próximo?

É assim que os seis pares subtrativos são formados. Em IV , IX , XL , XC , CD e CM , um símbolo menor vem antes de um maior, e o par vale o maior menos o menor. Subtrair o primeiro símbolo e adicionar o segundo resulta exatamente nesse valor, e nenhum outro lugar em um numeral válido tem um símbolo menor antes de um maior.

FácilMatemática e simulação Hashing

+10

Os numerais romanos usam sete símbolos: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 e M = 1000. Os símbolos são escritos do maior para o menor e somados, exceto em seis pares subtrativos, nos quais um símbolo menor vem primeiro e é subtraído do maior: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 e CM = 900.

Você recebe um numeral romano válido s. Retorne o inteiro que ele representa.

Função

romanToInt(s: string) → integer

sstring: um numeral romano válido em letras maiúsculas
Retornainteger: o valor do numeral, de 1 a 3999

Restrições

1 ≤ s.length ≤ 15
s contém apenas os caracteres I, V, X, L, C, D e M.
s é um numeral romano válido para um valor de 1 a 3999.

Exemplos

Entrada: s = "XXVII"
Saída: 27
Explicação: XX é 10 + 10, V é 5 e II é 1 + 1, então o total é 27. Nenhum símbolo é seguido por um maior, então todos os símbolos são somados.

Entrada: s = "CDXLIV"
Saída: 444
Explicação: O numeral é composto por três pares subtrativos em sequência: CD é 400, XL é 40 e IV é 4, o que resulta em 444.

Entrada: s = "MCDXCII"
Saída: 1492
Explicação: M é 1000, CD é 400, XC é 90 e II é 2, então o numeral é 1492. Pares e símbolos simples podem ser combinados livremente.

+22 testes ocultos ao enviar

Para ir além

Você consegue escrever o inverso, convertendo um número inteiro de 1 a 3999 em seu numeral romano?

Dicas

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

0 de 3 abertas

Solução

A maior parte de um numeral é uma soma simples, então o problema todo é identificar os seis pares subtrativos. Você pode procurá-los como tokens de duas letras ou usar a única regra que abrange os seis: um símbolo com valor menor que o do símbolo à sua direita é subtraído. De qualquer forma, uma única passagem por no máximo 15 caracteres fornece a resposta.

Leia os pares subtrativos como tokens

Intuição

Pense no numeral como uma sequência de tokens. A maioria dos tokens tem um símbolo, e seis têm dois símbolos: IV, IX, XL, XC, CD e CM. Divida a string nesses tokens, some seus valores e você terá o número.

Em cada posição, observe primeiro os próximos dois caracteres. Se eles formarem um dos seis pares, some o valor do par e avance sobre os dois. Caso contrário, some o valor do símbolo único e avance um caractere. MCDXCII se divide em M, CD, XC, I, I: 1000 + 400 + 90 + 1 + 1 = 1492.

A verificação do par precisa vir primeiro. Se você ler o X de XC sozinho, soma 10 e depois 100, obtendo 110 em vez de 90. A verificação também é segura: em um numeral válido, um símbolo menor aparece imediatamente antes de um maior somente dentro de um desses seis pares, então todo par que você encontrar é válido.

Cada etapa consome um ou dois caracteres, então o loop é executado no máximo 15 vezes. As duas tabelas têm tamanho fixo, então o espaço extra é constante.

Algoritmo

Crie uma tabela para os seis pares e outra para os sete símbolos individuais.
Comece no índice 0 com um total de 0.
Se os dois caracteres no índice formarem um par, some o valor do par e avance o índice em 2.
Caso contrário, some o valor do símbolo individual e avance o índice em 1.
Quando o índice ultrapassar o final, retorne o 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

Compare cada símbolo com o próximo

Intuição

Observe os seis pares novamente. Em todos eles, o primeiro símbolo vale menos que o segundo, e o valor do par é o segundo menos o primeiro. Portanto, você pode descartar a tabela de pares e usar uma única regra: se um símbolo vale menos que o símbolo à sua direita, subtraia-o; caso contrário, some-o. CM se torna -100 + 1000 = 900, o mesmo valor obtido pela leitura dos tokens.

Percorra MCDXCII. M é seguido por um C menor, então some 1000. C é seguido por um D maior, então subtraia 100: o total é 900. Some D para chegar a 1400. X é seguido por um C maior, então subtraia 10: 1390. Some C: 1490. O primeiro I é seguido por outro I igual, então some-o: 1491. O último I não tem vizinho, então some-o também: 1492.

A comparação deve ser estritamente menor que. Símbolos vizinhos iguais são sempre somados, o que faz com que II seja 2 e XX seja 20. A regra está correta pelo mesmo motivo que a leitura dos tokens: em um numeral válido, um símbolo menor aparece imediatamente antes de um maior somente como a primeira metade de um par subtrativo.

Você examina cada caractere uma vez e mantém um total acumulado, então o tempo é O(n) e o espaço extra é O(1). Esta versão precisa apenas dos valores dos sete símbolos e de uma comparação por caractere.

Algoritmo

Armazene o valor de cada um dos sete símbolos.
Percorra os índices de s mantendo um total acumulado que começa em 0.
Se o próximo símbolo existir e valer mais do que o atual, subtraia o valor atual.
Caso contrário, some o valor atual.
Retorne o total após o loop.

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

Armadilhas e casos extremos

A regra é curta, então os erros estão nos detalhes.

Usar menor que ou igual em vez de estritamente menor que. Então II resulta em 0 e XX em 0, porque cada primeiro símbolo é subtraído.
Ler o próximo símbolo no último caractere. s[i+1] não existe nessa posição; verifique i+1 em relação ao comprimento primeiro e sempre some o último símbolo.
Na versão com tokens, tentar os símbolos individuais antes dos pares. XC então é lido como 10 + 100 = 110.
Detectar o par apenas no segundo símbolo. Se você já somou o I de IV, precisa subtraí-lo duas vezes, 1 + 5 - 2 × 1 = 4. Comparar com o próximo símbolo evita essa correção.
Esquecer que as strings em Lua e R começam no índice 1, então o último símbolo está em #s ou nchar(s).

Perguntas frequentes4

Qual é a complexidade de tempo da conversão de algarismos romanos para inteiros?

As duas abordagens leem cada caractere uma vez, então o tempo é O(n) para um numeral de n caracteres. O espaço extra é O(1), porque as tabelas de consulta têm tamanho fixo. Um numeral de 1 a 3999 tem no máximo 15 caracteres, então, na prática, o trabalho é mínimo.

Por que você subtrai um símbolo que é menor que o próximo?

É assim que os seis pares subtrativos são formados. Em IV, IX, XL, XC, CD e CM, um símbolo menor vem antes de um maior, e o par vale o maior menos o menor. Subtrair o primeiro símbolo e adicionar o segundo resulta exatamente nesse valor, e nenhum outro lugar em um numeral válido tem um símbolo menor antes de um maior.

Você consegue converter um numeral romano da direita para a esquerda?

Sim. Percorra do último símbolo até o primeiro e lembre-se do valor do símbolo que você leu antes, aquele à direita. Se o símbolo atual valer menos do que aquele, subtraia-o; caso contrário, some-o. É a mesma regra da versão da esquerda para a direita, vista do outro lado.

Esta solução verifica se o numeral é válido?

Não. O problema garante um numeral válido, então o código apenas soma e subtrai. Dada uma string inválida como IIII ou VV, ele ainda retorna um número: 4 e 10. Para validar, converta o resultado de volta para um numeral e compare-o com a entrada.

Python

def romanToInt(s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "XXVII"

Esperado