## Monday, July 13, 2015

### LeetCode OJ - Integer to Roman

Problem:

Solution:

The Roman numericals is not defined in the problem, so I look it up here for a definition. We more or less know about the Roman numericals, but a precise definition is different. Here we adhere to the standard.

The key to the translation is that it is 'digit' to 'digit'.

We have, basically, these translation tables

 1 I 2 II 3 III 4 IV 5 V 6 VI 7 VII 8 VIII 9 IX

 10 X 20 XX 30 XXX 40 XL 50 L 60 LX 70 LXX 80 LXXX 90 XC

 100 C 200 CC 300 CCC 400 CD 500 D 600 DC 700 DCC 800 DCCC 900 CM

1,000 is M.

Note the similarity of these tables, so I just parameterized them.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/integer-to-roman/

#include "LEET_INTEGER_TO_ROMAN.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_INTEGER_TO_ROMAN
{
class Solution
{
private:
void intToRoman(int num, ostringstream& os, char i, char v, char x)
{
if (num <= 3)
{
for (int c = 0; c < num; c++)
{
os << i;
}
} else if (num == 4)
{
os << i;
os << v;
}
else if (num <= 8)
{
os << v;
intToRoman(num - 5, os, i, v, x);
}
else if (num == 9)
{
os << i;
os << x;
}

}
public:
string intToRoman(int num)
{
ostringstream os;
if (num < 10)
{
intToRoman(num, os, 'I', 'V', 'X');
}
else if (num < 100)
{
intToRoman((num / 10 ) % 10, os, 'X', 'L', 'C');
intToRoman((num / 1  ) % 10, os, 'I', 'V', 'X');
}
else
{
while (num >= 1000)
{
os << 'M';
num -= 1000;
}
intToRoman((num / 100) % 10, os, 'C', 'D', 'M');
intToRoman((num / 10 ) % 10, os, 'X', 'L', 'C');
intToRoman((num / 1  ) % 10, os, 'I', 'V', 'X');
}
return os.str();
}
};

string intToRoman(int num)
{
Solution s;
return s.intToRoman(num);
}
};

using namespace _LEET_INTEGER_TO_ROMAN;

int LEET_INTEGER_TO_ROMAN()
{
Solution s;
for (int i = 1; i <= 3999; i++)
{
cout << i << "\t" << s.intToRoman(i) << endl;
}
return 0;
}