Konverze Roman to Integer
Zkuste to na praxi GFG 
Výstup
Výstup
Vzhledem k řetězci S představujícím římskou číslici zjistí, že je to odpovídající celočíselná hodnota.
Římské číslice se vytvářejí pomocí následujících symbolů: i = 1 V = 5 x = 10 l = 50 c = 100 d = 500 a M = 1000.
Čísla jsou obvykle tvořena kombinací těchto symbolů zleva doprava přidávání nebo odečtení jejich hodnot na základě konkrétních pravidel.
Jak funguje konverze?
- Pokud přijde symbol menší hodnoty před odečtením. Jinak přidáme.
- V IV I přichází dříve, než V a V má větší hodnotu 5. Náš výsledek je tedy 5 - 1 = 4.
- Ve VI V přichází dříve, než já a já máme menší hodnotu 1. Náš výsledek je tedy 5 + 1 = 6.
- V II máme stejné hodnoty, takže přidáme a dostaneme 1 + 1 = 2
- V případě více než 2 znaků procházíme zleva doprava a skupinu pouze tehdy, když uvidíme po znaku menší hodnoty znak s větší hodnotou. Například MXVII je 1000 + 10 + 5 + 1 + 1 = 1017. A xlvii je (50 - 10) + 5 + 1 + 1 = 47. Všimněte si, že L je větší a přichází po X.
Příklady:
Vstup: s = 'ix'
Výstup: 9
Vysvětlení: IX je římský symbol, který představuje 10 - 1 = 9Vstup: s = 'xl'
Výstup: 40
Vysvětlení: XL je římský symbol, který představuje 50 - 10 = 40Vstup: s = 'mcmiv'
Výstup: 1904
Vysvětlení: M je 1000 cm je 1000 - 100 = 900 a IV je 4. Takže máme celkem 1000 + 900 + 4 = 1904
Obsah
- [Očekávaný přístup 1] Pomocí iterativního srovnání - O (n) Čas a O (1) prostor
- [Očekávaný přístup 2] Použití hashování - O (n) Čas a O (1) prostor
[Očekávaný přístup 1] Pomocí iterativního srovnání - O (n) Čas a O (1) prostor
C++Myšlenka přeměny římské číselného na celé číslo je to, že musíme procházet strunou zleva doprava. Pro každý symbol jej porovnejte s dalším symbolem (pokud existuje). Pokud je aktuální symbol větší nebo roven dalšímu symbolu, přidejte k výsledku svou hodnotu. Jinak odečte svou hodnotu od hodnoty dalšího symbolu a přidejte výsledek k celkovému a přeskočte další symbol.
#include using namespace std ; // this function returns value of a Roman symbol int value ( char r ) { if ( r == 'I' ) return 1 ; if ( r == 'V' ) return 5 ; if ( r == 'X' ) return 10 ; if ( r == 'L' ) return 50 ; if ( r == 'C' ) return 100 ; if ( r == 'D' ) return 500 ; if ( r == 'M' ) return 1000 ; return -1 ; } // returns decimal value of roman numeral int romanToDecimal ( string & s ) { int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // get value of current symbol int s1 = value ( s [ i ]); // Compare with the next symbol if it exists if ( i + 1 < s . length ()) { int s2 = value ( s [ i + 1 ]); // if current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and skip // next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } int main () { string s = 'IX' ; cout < < romanToDecimal ( s ) < < endl ; return 0 ; }
Java class GfG { // this function returns value of a Roman symbol static int value ( char r ) { if ( r == 'I' ) return 1 ; if ( r == 'V' ) return 5 ; if ( r == 'X' ) return 10 ; if ( r == 'L' ) return 50 ; if ( r == 'C' ) return 100 ; if ( r == 'D' ) return 500 ; if ( r == 'M' ) return 1000 ; return - 1 ; } // returns decimal value of roman numeral static int romanToDecimal ( String s ) { int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { //get value of current symbol int s1 = value ( s . charAt ( i )); // compare with the next symbol if it exists if ( i + 1 < s . length ()) { int s2 = value ( s . charAt ( i + 1 )); // If current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and skip // next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } public static void main ( String [] args ) { String s = 'IX' ; System . out . println ( romanToDecimal ( s )); } }
Python # this function returns value of a Roman symbol def value ( r ): if r == 'I' : return 1 if r == 'V' : return 5 if r == 'X' : return 10 if r == 'L' : return 50 if r == 'C' : return 100 if r == 'D' : return 500 if r == 'M' : return 1000 return - 1 # returns decimal value of roman numeral def romanToDecimal ( s ): res = 0 i = 0 while i < len ( s ): # get value of current symbol s1 = value ( s [ i ]) # compare with the next symbol if it exists if i + 1 < len ( s ): s2 = value ( s [ i + 1 ]) # if current value is greater or equal # add it to result if s1 >= s2 : res += s1 else : # else add the difference and # skip next symbol res += ( s2 - s1 ) i += 1 else : res += s1 i += 1 return res if __name__ == '__main__' : s = 'IX' print ( romanToDecimal ( s ))
C# using System ; class GfG { // this function returns value of a Roman symbol static int value ( char r ) { if ( r == 'I' ) return 1 ; if ( r == 'V' ) return 5 ; if ( r == 'X' ) return 10 ; if ( r == 'L' ) return 50 ; if ( r == 'C' ) return 100 ; if ( r == 'D' ) return 500 ; if ( r == 'M' ) return 1000 ; return - 1 ; } // returns decimal value of roman numeral static int romanToDecimal ( string s ) { int res = 0 ; for ( int i = 0 ; i < s . Length ; i ++ ) { // get value of current symbol int s1 = value ( s [ i ]); // compare with the next symbol if it exists if ( i + 1 < s . Length ) { int s2 = value ( s [ i + 1 ]); // if current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and skip // next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } static void Main () { string s = 'IX' ; Console . WriteLine ( romanToDecimal ( s )); } }
JavaScript // this function returns value of a Roman symbol function value ( r ) { if ( r === 'I' ) return 1 ; if ( r === 'V' ) return 5 ; if ( r === 'X' ) return 10 ; if ( r === 'L' ) return 50 ; if ( r === 'C' ) return 100 ; if ( r === 'D' ) return 500 ; if ( r === 'M' ) return 1000 ; return - 1 ; } // returns decimal value of roman numeral function romanToDecimal ( s ) { let res = 0 ; for ( let i = 0 ; i < s . length ; i ++ ) { // get value of current symbol let s1 = value ( s [ i ]); // compare with the next symbol if it exists if ( i + 1 < s . length ) { let s2 = value ( s [ i + 1 ]); // if current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and // skip next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } // Driver Code let s = 'IX' ; console . log ( romanToDecimal ( s ));
Výstup
9
[Očekávaný přístup 2] Použití hashování - O (n) Čas a O (1) prostor
C++K uložení hodnot římských symbolů můžeme použít hashovací mapu nebo slovník. A vyřešit problém, který musíme iterovat řetězem a pro každý symbol zkontrolujte, zda je aktuální hodnota menší než další hodnota. Pokud ano, odečtěte aktuální hodnotu od další hodnoty a přidejte výsledek k celkovému počtu. Jinak přidejte aktuální hodnotu k celkovému počtu.
#include #include using namespace std ; int romanToDecimal ( string & s ) { unordered_map < char int > romanMap = {{ 'I' 1 } { 'V' 5 } { 'X' 10 } { 'L' 50 } { 'C' 100 } { 'D' 500 } { 'M' 1000 }}; int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . length () && romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]) { res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]]; // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap [ s [ i ]]; } } return res ; } int main () { string s = 'IX' ; cout < < romanToDecimal ( s ) < < endl ; return 0 ; }
Java import java.util.HashMap ; class GfG { static int romanToDecimal ( String s ) { HashMap < Character Integer > romanMap = new HashMap <> (); romanMap . put ( 'I' 1 ); romanMap . put ( 'V' 5 ); romanMap . put ( 'X' 10 ); romanMap . put ( 'L' 50 ); romanMap . put ( 'C' 100 ); romanMap . put ( 'D' 500 ); romanMap . put ( 'M' 1000 ); int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . length () && romanMap . get ( s . charAt ( i )) < romanMap . get ( s . charAt ( i + 1 ))) { res += romanMap . get ( s . charAt ( i + 1 )) - romanMap . get ( s . charAt ( i )); // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap . get ( s . charAt ( i )); } } return res ; } public static void main ( String [] args ) { String s = 'IX' ; System . out . println ( romanToDecimal ( s )); } }
Python def romanToDecimal ( s ): romanMap = { 'I' : 1 'V' : 5 'X' : 10 'L' : 50 'C' : 100 'D' : 500 'M' : 1000 } res = 0 i = 0 while i < len ( s ): # if the current value is less than the next value # subtract current from next and add to res if i + 1 < len ( s ) and romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]: res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]] # skip the next symbol i += 1 else : # otherwise add the current value to res res += romanMap [ s [ i ]] i += 1 return res if __name__ == '__main__' : s = 'IX' print ( romanToDecimal ( s ))
C# using System ; using System.Collections.Generic ; class GfG { static int romanToDecimal ( string s ) { // create a map to store the Roman numeral values Dictionary < char int > romanMap = new Dictionary < char int > { { 'I' 1 } { 'V' 5 } { 'X' 10 } { 'L' 50 } { 'C' 100 } { 'D' 500 } { 'M' 1000 } }; int res = 0 ; for ( int i = 0 ; i < s . Length ; i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . Length && romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]) { res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]]; // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap [ s [ i ]]; } } return res ; } static void Main () { string s = 'IX' ; Console . WriteLine ( romanToDecimal ( s )); } }
JavaScript function romanToDecimal ( s ) { // create a map to store the Roman numeral values const romanMap = { 'I' : 1 'V' : 5 'X' : 10 'L' : 50 'C' : 100 'D' : 500 'M' : 1000 }; let res = 0 ; for ( let i = 0 ; i < s . length ; i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . length && romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]) { res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]]; // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap [ s [ i ]]; } } return res ; } // Driver Code let s = 'IX' ; console . log ( romanToDecimal ( s ));
Výstup
9
