ROMAN NA CELÉ KONVERZIE

Vyskúšajte to v praxi GFG ' title=

Vzhľadom na reťazec S predstavujúcim rímske číslice nájdete zodpovedajúcu celočíselnú hodnotu.
Rímske číslice sa tvoria pomocou nasledujúcich symbolov: i = 1 v = 5 x = 10 l = 50 c = 100 d = 500 a m = 1000.
Čísla sa zvyčajne tvoria kombináciou týchto symbolov zľava doprava alebo odpočítaním svojich hodnôt na základe konkrétnych pravidiel.

algoritmus pre bfs

Ako funguje konverzia?

Ak príde symbol menšej hodnoty skôr, ako odpočítame. Inak pridáme.
V IV I prichádza pred V a V, ktorý má väčšiu hodnotu 5. Takže náš výsledok je 5 - 1 = 4.
Vo VI V prichádza skôr, ako i a ja máme menšiu hodnotu 1. Takže náš výsledok je 5 + 1 = 6.
V II máme rovnaké hodnoty, takže pridávame a získame 1 + 1 = 2
V prípade viac ako 2 znakov prechádzame zľava doprava a zoskupujeme iba vtedy, keď vidíme znak väčšieho hodnoty po znaku menšej hodnoty. Napríklad MXVII je 1000 + 10 + 5 + 1 + 1 = 1017. A XLVII je (50 - 10) + 5 + 1 + 1 = 47. Všimnite si, že L je väčší a prichádza po X.

Príklady:

Vstup: s = 'ix'
Výstup: 9
Vysvetlenie: Ix je rímsky symbol, ktorý predstavuje 10 - 1 = 9
Vstup: s = 'xl'
Výstup: 40
Vysvetlenie: XL je rímsky symbol, ktorý predstavuje 50 - 10 = 40
latex s veľkosťou písma
Vstup: S = 'McMiv'
Výstup: 1904
Vysvetlenie: M je 1000 cm je 1000 - 100 = 900 a IV je 4. Takže máme celkovú hodnotu ako 1 000 + 900 + 4 = 1904

Tabuľka obsahu

[Očakávaný prístup 1] pomocou iteračného porovnania - O (n) čas a O (1) priestor
[Očakávaný prístup 2] Použitie hashing - O (n) čas a O (1) priestor

[Očakávaný prístup 1] pomocou iteračného porovnania - O (n) čas a O (1) priestor

Myšlienka previesť rímske číslice na celé číslo je, že musíme prejsť reťazcom zľava doprava. Pre každý symbol ho porovnajte s ďalším symbolom (ak existuje). Ak je aktuálny symbol väčší alebo rovný ďalšiemu symbolu, pridajte jeho hodnotu k výsledku. V opačnom prípade odpočítajte svoju hodnotu od hodnoty nasledujúceho symbolu a pridajte výsledok k celkovému súčtu a preskočte ďalší symbol.

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

Výstup

[Očakávaný prístup 2] Použitie hashing - O (n) čas a O (1) priestor

Na ukladanie hodnôt rímskych symbolov môžeme použiť hashovú mapu alebo slovník. A na vyriešenie problému musíme iterovať prostredníctvom reťazca a pre každú kontrolu symbolu, či je aktuálna hodnota nižšia ako ďalšia hodnota. Ak je to tak, odpočítajte aktuálnu hodnotu od ďalšej hodnoty a pridajte výsledok k celkovej hodnote. V opačnom prípade pridajte aktuálnu hodnotu k celkovej hodnote.
podreťazec metódy java

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