[LeetCode] Integer to Roman 整数转化成罗马数字

IVXLCDM

Symbol       Value

I             1

V             5

X             10

L             50

C             100

D             500

M             1000

IIXIIXIIXXVIIXXVII

IIIIIVIX

IVXXLCCDM

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3

Output: "III"

Example 2:

Input: 4

Output: "IV"

Example 3:

Input: 9

Output: "IX"

Example 4:

Input: 58

Output: "LVIII"

Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: 1994

Output: "MCMXCIV"

Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

之前那篇文章写的是罗马数字转化成整数 Roman to Integer， 这次变成了整数转化成罗马数字，基本算法还是一样。由于题目中限定了输入数字的范围 (1 - 3999), 使得题目变得简单了不少。

I - 1

V - 5

X - 10

L - 50

C - 100

D - 500

M - 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 最后一类。每一位上的情况都是类似的，代码如下：

解法一：

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

解法二：

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

解法三：

Github 同步地址：

类似题目：

参考资料：