KONWERSJA LICZBY RZYMSKIEJ NA LICZBĘ CAŁKOWITĄ

Wypróbuj w praktyce GfG ' title=

Biorąc pod uwagę ciąg s reprezentujący cyfrę rzymską, znajdź odpowiadającą jej wartość całkowitą.
Cyfry rzymskie tworzy się za pomocą następujących symboli: I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 i M = 1000.
Liczby tworzy się zazwyczaj poprzez połączenie tych symboli od lewej do prawej, dodając lub odejmując ich wartości w oparciu o określone zasady.

jak zamienić string na int

Jak działa konwersja?

Jeśli przed odjęciem pojawi się mniejszy symbol wartości. W przeciwnym razie dodajemy.
W IV I występuje przed V, a V ma większą wartość 5. Zatem nasz wynik to 5 – 1 = 4.
W VI V występuje przed I, a I ma mniejszą wartość 1. Zatem nasz wynik to 5 + 1 = 6.
W II mamy te same wartości, więc dodajemy i otrzymujemy 1 + 1 = 2
W przypadku więcej niż 2 znaków przechodzimy od lewej do prawej i grupujemy tylko wtedy, gdy po znaku o mniejszej wartości widzimy znak o większej wartości. Na przykład MXVII to 1000 + 10 + 5 + 1 + 1 = 1017. XLVII to (50 - 10) + 5 + 1 + 1 = 47. Zauważ, że L jest większe i występuje po X.

Przykłady:

Wejście: s = „IX”
Wyjście: 9
Wyjaśnienie: IX to rzymski symbol reprezentujący 10 – 1 = 9
co jest w przypadku sql
Wejście: s = „XL”
Wyjście: 40
Wyjaśnienie: XL to rzymski symbol, który reprezentuje 50 - 10 = 40
Wejście: s = „MCMIV”
Wyjście: 1904
Wyjaśnienie: M to 1000 CM to 1000 - 100 = 900, a IV to 4. Zatem mamy razem 1000 + 900 + 4 = 1904

Spis treści

kiedy kończy się q1

[Oczekiwane podejście 1] Korzystanie z porównania iteracyjnego - czas O(n) i przestrzeń O(1)
[Oczekiwane podejście 2] Korzystanie z funkcji mieszania — czas O(n) i przestrzeń O(1).

[Oczekiwane podejście 1] Korzystanie z porównania iteracyjnego - czas O(n) i przestrzeń O(1)

Pomysł na konwersję cyfry rzymskiej na liczbę całkowitą polega na tym, że musimy przejść przez ciąg znaków od lewej do prawej. Dla każdego symbolu porównaj go z kolejnym symbolem (jeśli istnieje). Jeśli bieżący symbol jest większy lub równy następnemu symbolowi, dodaj jego wartość do wyniku. W przeciwnym razie odejmij jego wartość od wartości następnego symbolu i dodaj wynik do sumy i pomiń następny 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));

Wyjście

[Oczekiwane podejście 2] Korzystanie z funkcji mieszania — czas O(n) i przestrzeń O(1).

Do przechowywania wartości symboli rzymskich możemy użyć mapy skrótów lub słownika. Aby rozwiązać problem, musimy iterować po ciągu i dla każdego symbolu sprawdzić, czy bieżąca wartość jest mniejsza niż następna wartość. Jeśli tak, odejmij bieżącą wartość od następnej wartości i dodaj wynik do sumy. W przeciwnym razie dodaj bieżącą wartość do sumy.

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