CONVERSIÓ ROMANA A ENTER

Proveu -ho a la pràctica GFG ' title=

Tenint en compte una cadena que representa un número romà de trobada que és el valor enter corresponent.
Els números romans es formen mitjançant els símbols següents: i = 1 V = 5 x = 10 L = 50 C = 100 D = 500 i M = 1000.
Els números es formen normalment combinant aquests símbols d’esquerra a dreta afegint o restant els seus valors en funció de regles específiques.

caràcter a cadena

Com funciona la conversió?

Si es produeix un símbol de valor menor abans de restar. En cas contrari, afegim.
A IV I arriba abans que V i V té un valor més gran 5. Per tant, el nostre resultat és de 5 - 1 = 4.
A VI V arriba abans que jo i jo tingui un valor menor. Així doncs, el nostre resultat és 5 + 1 = 6.
A II tenim els mateixos valors per afegir i obtenir 1 + 1 = 2
En cas de més de 2 caràcters, travessem d’esquerra a dreta i grup només quan veiem un caràcter de valor més gran després d’un caràcter de valor menor. Per exemple, MXVII és 1000 + 10 + 5 + 1 + 1 = 1017. I XLVII és (50 - 10) + 5 + 1 + 1 = 47. Tingueu en compte que L és més gran i arriba després de X.

Exemples:

Entrada: s = 'ix'
Sortida: 9
Explicació: Ix és un símbol romà que representa 10 - 1 = 9
Entrada: s = 'xl'
Sortida: 40
Explicació: XL és un símbol romà que representa 50 - 10 = 40
Entrada: S = 'McMiv'
Sortida: 1904
Explicació: M és 1000 cm és 1000 - 100 = 900 i IV és 4. Per tant, tenim total com a 1000 + 900 + 4 = 1904
enter a cadena

Taula de contingut

[Enfocament esperat 1] Utilitzant la comparació iterativa - O (n) Temps i O (1) Espai
[Aproximació esperada 2] Utilitzant el temps de hashing - O (n) i O (1) Espai

[Enfocament esperat 1] Utilitzant la comparació iterativa - O (n) Temps i O (1) Espai

La idea de convertir un número romà en un nombre enter és que hem de recórrer la cadena d’esquerra a dreta. Per a cada símbol, compareu -lo amb el següent símbol (si existeix). Si el símbol actual és superior o igual al següent símbol, afegiu el seu valor al resultat. En cas contrari, resteu el seu valor del valor del següent símbol i afegiu el resultat al total i salteu el següent símbol.
repositori maven

C++

#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))

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));

Producció

[Aproximació esperada 2] Utilitzant el temps de hashing - O (n) i O (1) Espai

Podem utilitzar un mapa de hash o un diccionari per emmagatzemar els valors dels símbols romans. I per resoldre el problema, hem de iterar a través de la cadena i per a cada símbol, comproveu si el valor actual és inferior al següent valor. Si és així, resteu el valor actual del següent valor i afegiu el resultat al total. En cas contrari, afegiu el valor actual al total.

C++

#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; }