Roman to Integer

Q: Perché sottrai un simbolo più piccolo del successivo?

È così che si formano le sei coppie sottrattive. In IV , IX , XL , XC , CD e CM , un simbolo più piccolo precede uno più grande e la coppia vale il simbolo più grande meno quello più piccolo. Sottrarre il primo simbolo e aggiungere il secondo dà esattamente quel valore, e in nessun’altra posizione di un numero valido un simbolo più piccolo precede uno più grande.

FacileMatematica e simulazione Hashing

+10

I numeri romani usano sette simboli: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 e M = 1000. I simboli si scrivono dal più grande al più piccolo e si sommano, tranne in sei coppie sottrattive, in cui un simbolo più piccolo viene prima e viene sottratto da quello più grande: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 e CM = 900.

Ti viene dato un numero romano valido s. Restituisci l'intero che rappresenta.

Funzione

romanToInt(s: string) → integer

sstring: un numero romano valido in lettere maiuscole
Restituisceinteger: il valore del numerale, da 1 a 3999

Vincoli

1 ≤ s.length ≤ 15
s contiene solo i caratteri I, V, X, L, C, D e M.
s è un numero romano valido per un valore da 1 a 3999.

Esempi

Input: s = "XXVII"
Output: 27
Spiegazione: XX è 10 + 10, V è 5 e II è 1 + 1, quindi il totale è 27. Nessun simbolo è seguito da uno più grande, quindi ogni simbolo viene sommato.

Input: s = "CDXLIV"
Output: 444
Spiegazione: Il numero è composto da tre coppie sottrattive in fila: CD vale 400, XL vale 40 e IV vale 4, per un totale di 444.

Input: s = "MCDXCII"
Output: 1492
Spiegazione: M è 1000, CD è 400, XC è 90 e II è 2, quindi il numero è 1492. Le coppie e i simboli singoli si combinano liberamente.

+22 test nascosti all’invio

Per approfondire

Riesci a scrivere il procedimento inverso, convertendo un numero intero da 1 a 3999 nel suo numero romano?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La maggior parte di un numero è una semplice somma, quindi il problema consiste tutto nell’individuare le sei coppie sottrattive. Puoi cercarle come token di due lettere oppure usare l’unica regola che le copre tutte e sei: un simbolo che vale meno di quello alla sua destra viene sottratto. In entrambi i casi, basta scorrere al massimo 15 caratteri una volta per ottenere la risposta.

Leggi le coppie sottrattive come gettoni

Intuizione

Immagina il numero come una sequenza di gettoni. La maggior parte dei gettoni è composta da un simbolo, mentre sei sono composti da due simboli: IV, IX, XL, XC, CD e CM. Dividi la stringa in questi gettoni, somma i loro valori e otterrai il numero.

A ogni posizione, guarda prima i due caratteri successivi. Se formano una delle sei coppie, aggiungi il valore della coppia e salta entrambi i caratteri. Altrimenti aggiungi il valore del singolo simbolo e salta un carattere. MCDXCII si divide in M, CD, XC, I, I: 1000 + 400 + 90 + 1 + 1 = 1492.

Il controllo della coppia deve essere eseguito per primo. Se leggi da solo la X di XC, aggiungi 10 e poi 100, ottenendo 110 invece di 90. Il controllo è anche sicuro: in un numero romano valido un simbolo più piccolo si trova subito prima di uno più grande solo all'interno di una di queste sei coppie, quindi ogni coppia che trovi è effettivamente valida.

Ogni passaggio consuma uno o due caratteri, quindi il ciclo viene eseguito al massimo 15 volte. Le due tabelle hanno una dimensione fissa, quindi lo spazio aggiuntivo è costante.

Algoritmo

Crea una tabella per le sei coppie e una per i sette simboli singoli.
Inizia dall'indice 0 con un totale di 0.
Se i due caratteri all'indice formano una coppia, aggiungi il valore della coppia e sposta l'indice di 2.
Altrimenti aggiungi il valore del simbolo singolo e sposta l'indice di 1.
Quando l'indice supera la fine, restituisci il totale.

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

Confronta ogni simbolo con quello successivo

Intuizione

Guarda di nuovo le sei coppie. In ognuna, il primo simbolo vale meno del secondo e la coppia vale il secondo meno il primo. Quindi puoi eliminare la tabella delle coppie e usare una sola regola: se un simbolo vale meno del simbolo alla sua destra, sottrailo; altrimenti aggiungilo. CM diventa -100 + 1000 = 900, lo stesso valore ottenuto leggendo i token.

Esamina MCDXCII. Dopo M c’è una C più piccola, quindi aggiungi 1000. Dopo C c’è una D più grande, quindi sottrai 100: il totale è 900. Aggiungi D per arrivare a 1400. Dopo X c’è una C più grande, quindi sottrai 10: 1390. Aggiungi C: 1490. Dopo la prima I c’è un’altra I uguale, quindi aggiungila: 1491. L’ultima I non ha un simbolo vicino, quindi aggiungila anche: 1492.

Il confronto deve essere strettamente minore. I simboli uguali adiacenti vengono sempre sommati, ed è così che II vale 2 e XX vale 20. La regola è corretta per lo stesso motivo per cui è corretto leggere i token: in un numero romano valido, un simbolo più piccolo precede immediatamente uno più grande solo come prima metà di una coppia sottrattiva.

Esamini ogni carattere una sola volta e mantieni un totale progressivo, quindi il tempo è O(n) e lo spazio aggiuntivo è O(1). Questa versione richiede solo i sette valori dei simboli e un confronto per carattere.

Algoritmo

Memorizza il valore di ciascuno dei sette simboli.
Esegui un ciclo sugli indici di s con un totale progressivo che parte da 0.
Se il simbolo successivo esiste e vale più di quello corrente, sottrai il valore corrente.
Altrimenti, aggiungi il valore corrente.
Restituisci il totale dopo il ciclo.

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

Trappole e casi limite

La regola è breve, quindi gli errori riguardano i suoi casi limite.

Usare minore o uguale invece di strettamente minore. In tal caso II risulta 0 e XX risulta 0, perché ogni primo simbolo viene sottratto.
Leggere il simbolo successivo sull'ultimo carattere. s[i+1] lì non esiste; controlla prima i+1 rispetto alla lunghezza e aggiungi sempre l'ultimo simbolo.
Nella versione con token, provare i simboli singoli prima delle coppie. XC viene quindi letto come 10 + 100 = 110.
Rilevare la coppia solo sul suo secondo simbolo. Se hai già aggiunto la I di IV, devi sottrarla due volte: 1 + 5 - 2 × 1 = 4. Confrontare con il simbolo successivo evita questa correzione.
Dimenticare che le stringhe di Lua e R iniziano dall'indice 1, quindi l'ultimo simbolo si trova in #s o nchar(s).

Domande frequenti4

Qual è la complessità temporale di Roman to Integer?

Entrambi gli approcci leggono ogni carattere una volta, quindi il tempo è O(n) per un numero di n caratteri. Lo spazio aggiuntivo è O(1), perché le tabelle di ricerca hanno dimensioni fisse. Un numero da 1 a 3999 ha al massimo 15 caratteri, quindi in pratica il lavoro è minimo.

Perché sottrai un simbolo più piccolo del successivo?

È così che si formano le sei coppie sottrattive. In IV, IX, XL, XC, CD e CM, un simbolo più piccolo precede uno più grande e la coppia vale il simbolo più grande meno quello più piccolo. Sottrarre il primo simbolo e aggiungere il secondo dà esattamente quel valore, e in nessun’altra posizione di un numero valido un simbolo più piccolo precede uno più grande.

Riesci a convertire un numero romano da destra a sinistra?

Sì. Procedi dall’ultimo simbolo al primo e ricorda il valore del simbolo letto prima, quello alla sua destra. Se il simbolo corrente vale meno di quello, sottrailo; altrimenti, aggiungilo. È la stessa regola della versione da sinistra a destra, vista dall’altro lato.

Questa soluzione verifica che il numerale sia valido?

No. Il problema garantisce un numero romano valido, quindi il codice esegue solo addizioni e sottrazioni. Se gli viene passata una stringa non valida come IIII o VV, restituisce comunque un numero, 4 e 10. Per convalidarla, converti il risultato di nuovo in un numero romano e confrontalo con l'input.

Python

def romanToInt(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "XXVII"

Atteso