leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

integer-to-romanV3Vector.cpp (1020B)

      1 #include <iostream>
      2 #include <map>
      3 using namespace std;
      4 
      5 //Leet Ratings
      6 //       Speed  Memory
      7 //Total  0ms    6MB    
      8 //Beats  100%   82.36%
      9 //
     10 //This is so much faster because I am using an array that does not have to 
     11 //sort each added element which is O(log(n)) for each insert.
     12 
     13 
     14 string intToRoman(int num) {
     15     pair<int, string> pairs[] = { 
     16         {1, "I"},
     17         {4, "IV"},
     18         {5, "V"},
     19         {9, "IX"},
     20         {10, "X"},
     21         {40, "XL"},
     22         {50, "L"},
     23         {90, "XC"},
     24         {100, "C"},
     25         {400, "CD"},
     26         {500, "D"},
     27         {900, "CM"},
     28         {1000, "M"} 
     29     };
     30     int list_size = sizeof(pairs) / sizeof(pairs[0]);
     31     string numeral = "";
     32     while(num > 0){
     33         for(int i = list_size - 1; i >= 0; --i){
     34             if(num >= pairs[i].first){
     35                 num -= pairs[i].first;
     36                 numeral += pairs[i].second;
     37                 ++i;
     38             }
     39         }
     40     }
     41     return numeral;
     42 }
     43 
     44 int main(){
     45     cout << intToRoman(134) << endl;
     46     return 0;
     47 }