leetcode

commit 0a7268c1e98e137356cddba07e60066682e59aa6
parent bd1b6300fe62f8abbe7c13e5baf6568f0201a546
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun,  9 Apr 2023 23:31:20 -0500

Completed integer to roman with array of pairs

Diffstat:
A
integer-to-roman/integer-to-romanV2Hash.cpp
 | 
64
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
integer-to-roman/integer-to-romanV3Vector.cpp
 | 
47
+++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 111 insertions(+), 0 deletions(-)
diff --git a/integer-to-roman/integer-to-romanV2Hash.cpp b/integer-to-roman/integer-to-romanV2Hash.cpp
@@ -0,0 +1,64 @@
+#include <iostream>
+#include <map>
+using namespace std;
+
+//Leet Ratings
+//       Speed  Memory
+//Total  27ms    13MB    
+//Beats  6.76%   6.11%
+// Since I already know the refrence values I should use a vector of pairs because this method
+// sorts them when entering the refrences in the map which is not necessary.
+
+
+
+string intToRoman(int num) {
+
+    //Create hashmap
+    map <int ,string> symbols;
+    symbols.insert({1, "I"});
+    symbols.insert({4, "IV"});
+    symbols.insert({5, "V"});
+    symbols.insert({9, "IX"});
+    symbols.insert({10, "X"});
+    symbols.insert({40, "XL"});
+    symbols.insert({50, "L"});
+    symbols.insert({90, "XC"});
+    symbols.insert({100, "C"});
+    symbols.insert({400, "CD"});
+    symbols.insert({500, "D"});
+    symbols.insert({900, "CM"});
+    symbols.insert({1000, "M"});
+    string numeral = "";
+    auto last_it = symbols.rbegin();
+    bool no_it = false;
+    while(num > 0){
+        for(auto it = symbols.rbegin() ; it != symbols.rend() ; ++it ){
+            
+            if(no_it){
+            it = last_it;
+            no_it = false;
+            }
+
+            if(num >= it->first){
+                num -= it->first;
+                numeral += it->second;
+                no_it = true;
+            }
+            last_it = it;
+        }
+        
+    }
+
+    return numeral;
+}
+
+
+int main(){
+
+
+
+
+    cout << intToRoman(134) << endl;
+    return 0;
+
+}
diff --git a/integer-to-roman/integer-to-romanV3Vector.cpp b/integer-to-roman/integer-to-romanV3Vector.cpp
@@ -0,0 +1,47 @@
+#include <iostream>
+#include <map>
+using namespace std;
+
+//Leet Ratings
+//       Speed  Memory
+//Total  0ms    6MB    
+//Beats  100%   82.36%
+//
+//This is so much faster because I am using an array that does not have to 
+//sort each added element which is O(log(n)) for each insert.
+
+
+string intToRoman(int num) {
+    pair<int, string> pairs[] = { 
+        {1, "I"},
+        {4, "IV"},
+        {5, "V"},
+        {9, "IX"},
+        {10, "X"},
+        {40, "XL"},
+        {50, "L"},
+        {90, "XC"},
+        {100, "C"},
+        {400, "CD"},
+        {500, "D"},
+        {900, "CM"},
+        {1000, "M"} 
+    };
+    int list_size = sizeof(pairs) / sizeof(pairs[0]);
+    string numeral = "";
+    while(num > 0){
+        for(int i = list_size - 1; i >= 0; --i){
+            if(num >= pairs[i].first){
+                num -= pairs[i].first;
+                numeral += pairs[i].second;
+                ++i;
+            }
+        }
+    }
+    return numeral;
+}
+
+int main(){
+    cout << intToRoman(134) << endl;
+    return 0;
+}