Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

 

之前那篇文章写的是罗马数字转化成整数(http://www.cnblogs.com/grandyang/p/4120857.html)， 这次变成了整数转化成罗马数字，基本算法还是一样。由于题目中限定了输入数字的范围(1 - 3999), 使得题目变得简单了不少。

基本字符	I	V	X	L	C	D	M
相应的阿拉伯数字表示为	1	5	10	50	100	500	1000

 

例如整数 1437 的罗马数字为 MCDXXXVII， 我们不难发现，千位，百位，十位和个位上的数分别用罗马数字表示了。 1000 - M, 400 - CD, 30 - XXX, 7 - VII。所以我们要做的就是用取商法分别提取各个位上的数字，然后分别表示出来：

100 - C

200 - CC

300 - CCC

400 - CD

500 - D

600 - DC

700 - DCC

800 - DCCC

900 - CM

我们可以分为四类，100到300一类，400一类，500到800一类，900最后一类。每一位上的情况都是类似的，代码如下：

 

解法一：

class Solution {public:    string intToRoman(int num) {        string res = "";        char roman[] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};        int value[] = {1000, 500, 100, 50, 10, 5, 1};                for (int n = 0; n < 7; n += 2) {            int x = num / value[n];            if (x < 4) {                for (int i = 1; i <= x; ++i) res += roman[n];            } else if (x == 4) res = res + roman[n] + roman[n - 1];            else if (x > 4 && x < 9) {                res += roman[n - 1];                for (int i = 6; i <= x; ++i) res += roman[n];            }            else if (x == 9) res = res + roman[n] + roman[n - 2];            num %= value[n];                    }        return res;    }};

 

本题由于限制了输入数字范围这一特殊性，故而还有一种利用贪婪算法的解法，建立一个数表，每次通过查表找出当前最大的数，减去再继续查表。参见代码如下：

 

解法二：

class Solution {public:    string intToRoman(int num) {        string res = "";        vector<int> val{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};        vector<string> str{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};        for (int i = 0; i < val.size(); ++i) {            while (num >= val[i]) {                num -= val[i];                res += str[i];            }        }        return res;    }};

 

下面这种方法个人感觉属于比较投机取巧的方法，把所有的情况都列了出来，然后直接按位查表，O(1)的时间复杂度啊，参见代码如下：

 

解法三：

class Solution {public:    string intToRoman(int num) {        string res = "";        vector<string> v1{"", "M", "MM", "MMM"};        vector<string> v2{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};        vector<string> v3{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};        vector<string> v4{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};        return v1[num / 1000] + v2[(num % 1000) / 100] + v3[(num % 100) / 10] + v4[num % 10];    }};

 

类似题目：

Roman to Integer

 

参考资料：

https://discuss.leetcode.com/topic/12384/simple-solution

https://discuss.leetcode.com/topic/20510/my-java-solution-easy-to-understand

 

LeetCode All in One 题目讲解汇总(持续更新中...)