I just have the free account at leetcode. I've been practicing some coding there in preparation for interviews. But I can't see the solution logic behind the IntegerToRoman conversion function. I solved both the leetcode Roman Numbers problems (Arabic -> roman, and roman -> Arabic). I made a solution of my own but its slower than most accepted leetcode solutions.
I would appreciate any feedback code review-wise on the solutions but the main goal is to make them faster somehow. Especially the IntToRoman seemed trickier when I got to coding it. The RomanToInt was tricky as well, but when I realized the reversal it seemed OK. I started to code it with a stack originally instead of the oldval, but variable is enough and stack isn't needed as such.
The main code:
int fasterRomanToInt(std::string s)
{
int romanSum{ 0 };
if (s.size() == 1)
{
return oneSizeRomans(s[0]);
}
else
{
int oldval = 0;
int i = s.length() - 1;
while (i >= 0)
{
char current = s[i];
int curval = oneSizeRomans(current);
if (curval >= oldval)
{
romanSum += curval;
}
else
{
romanSum -= curval;
}
oldval = curval;
--i;
}
return romanSum;
}
}
std::string intToRoman(int num)
{
std::map<int, std::string> ArabicvalueToRomans
{
{1000, "M"},
{900, "CM"},
{500, "D"},
{400, "CD"},
{100, "C"},
{90, "XC"},
{50, "L"},
{40, "XL"},
{10, "X"},
{9, "IX"},
{8, "VIII"},
{7, "VII"},
{6, "VI"},
{5, "V"},
{4, "IV"},
{3, "III"},
{2, "II"},
{1, "I"}
};
std::vector<int> romanSpecials{ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 8,7,6,5,4,3,2,1 };
int arabic = num;
std::string result = "";
while (arabic > 0)
{
int d = seekLargestPossible(romanSpecials, arabic);
int r = arabic % d;
std::string characters = processToRoman(d, ArabicvalueToRomans);
arabic -= d;
result += characters;
}
return result;
}
Here's a couple helper functions for intToRoman:
int seekLargestPossible(std::vector<int>& vecRef, int a)
{
// input bigger than biggest divisor so use 1000
if (a >= 1000)
{
return 1000;
}
// seek the biggest divisor that is smallerorequal than the A inputvalue
for (auto iter = vecRef.begin(); iter != vecRef.end(); iter++)
{
auto key = *(iter);
if (key <= a)
{
return key;
}
}
throw "something went bad in seekLargestPossible";
}
std::string processToRoman(int value, std::map<int, std::string>& mapRef)
{
// if cannot access romanstr in map with key, throws which is good
// shuldnt be happening tho
std::string s = mapRef.at(value);
return s;
}
And here's a helper function for RomanToInt:
int oneSizeRomans(char c)
{
/* I 1
V 5
X 10
L 50
C 100
D 500
M 1000*/
switch (c)
{
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C':return 100;
case 'D':return 500;
case 'M':return 1000;
default:
throw "bad things one size romans func";
break;
}
}
std::mapis slow unless your benchmark shows it to be faster than saystd::vector. Only ever use it where it performs better, or when it makes code simpler but the performance hit doesn't matter much. For small maps that would fit into a couple of cache lines if they were a vector, the vector always wins: less page misses, less data cache misses, less code cache misses since the code is smaller, less branch mispredictions. \$\endgroup\$