「前端刷题」12. 整数转罗马数字-一一网

这是我参与8月更文挑战的第12天，活动详情查看：8月更文挑战

题目

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
复制代码

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

示例 1:

输入: num = 3
输出: “III”

示例 2:

输入: num = 4
输出: “IV”

示例 3:

输入: num = 9
输出: “IX”

示例 4:

输入: num = 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= num <= 3999

解题思路

思路1

给定一个整数，将其转为罗马数字，输入数字在1到3999范围内。
已知：罗马数字包含以下七种字符：I,V,X,L,C,D,M

    //转换表为：
    字符     数值     进位
     I       1       个位值为1
     V       5       个位值为5
     X       10      十位值为1
     L       50      十位值为5
     C       100     百位值为1
     D       500     百位值为5
     M       1000    千位值为1
复制代码

一般情况下数字组成：大的数字位+小的数字位 —- <1>
例如：6：VI 7:VII 8:VIII
可知：数值大小 == 大的数字位+小的数字位
再如：1:I 2:II 3: III
但当罗马数字进位值（个、十、百、千）== 9 或 == 4 时，数字组成变为：小的数字+大的数字 —- <2>

    // 例如：
      4:IV   9:IX 
     40:XL  90:XC  
    400:CD 900:CM
复制代码

可知：数值大小 == 大的数字位-小的数字位
- 由上述可以推出罗马数字每个进位值1-9的表示法：
- 个位【1-9】：I、II、III、IV、V、VI、VII、VIII、IX （对应阿拉伯数字 X%10）
- 十位【1-9】：X、XX、XXX、XL、L、LX、LXX、LXXX、XC （对应阿拉伯数字 (X%100)/10）
- 百位【1-9】：C、CC、CCC、CD、D、DC、DCC、DCCC、CM （对应阿拉伯数字 (X%1000)/100）
- 千位【1-9】：M、MM、MMM （对应阿拉伯数字 X/1000）
由以上可知一个阿拉伯数字 => 罗马数字
num => num/1000 + (num%1000)/100 +(num%100)/10 + num%10

代码1

/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    var Q = ["", "M", "MM", "MMM"];
    var B = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
    var S = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
    var G = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
    return Q[Math.floor(num/1000)] + B[Math.floor((num%1000)/100)] + S[Math.floor((num%100)/10)] + G[num%10];
};
复制代码

思路2

根据题意，我们可以得知罗马数字字符共 777 个，然后，再加上 444，999，404040，909090，400400400，900900900 这六类特殊表示规则，这里的特殊指的是较小数在较大数左则。

再者，题意规定数字范围为 1<=num<=39991 <= num <= 39991<=num<=3999 ，所以，常用解法大致分为：哈希表，字典法。

字典法相对简单，如下所示：

数字	千	百	十	个
0	–	–	–	–
1	M	C	X	I
2	MM	CC	XX	II
3	MMM	CCC	XXX	III
4	–	CD	XL	IV
5	–	D	L	V
6	–	DC	LX	VI
7	–	DCC	LXX	VII
8	–	DCCC	LXXX	VIII
9	–	CM	XC	IX

假设我们要转换 396839683968 为罗马数字，则根据千百十个位和当前位数字交叉点的罗马数字来组装即可，如下所示：

3[千位][MMM] + 9[百位][CM] + 6[十位][LX] + 8[个位][VIII] = MMMCMLXVIII

由于字典法思路比较简单，所以就不画图了。

而哈希表在于，只罗列出关键的 777 种数字字符，加上 666 种特殊数字所对应的罗马数字，也就是 [1000,900,500,400,100,90,50,40,10,9,5,4,1][1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1][1000,900,500,400,100,90,50,40,10,9,5,4,1] 。然后遍历该数组，每一个数都和 numnumnum 作比较，大于则跳过，小于则在 romanromanroman 结果集存入其对应的罗马数字，最终 romanromanroman 数组字符化，就是最终答案。

关于罗马数字的小知识点：

数字上方画一根横线，代表该数字乘以 100010001000 倍。
在 141414 世纪时，法国的查理五世下令不允许使用 ⅣⅣⅣ，而必须改为 IIIIIIIIIIII，因为他觉得 IVIVIV 是众神之主朱庇特的名称简写（在古典拉丁文中，JJJ 和 III 同为 III，UUU 和 VVV 同为 VVV，因此 IVIVIV 即 JUJUJU，朱庇特 JupiterJupiterJupiter 的简写），他不希望众神之主的名字像个数字。

图解演示

代码2

// 哈希表解法
var intToRoman = function(num) {
    let values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1],
        valueSymbols = new Map([
            [1000, "M"], [900, "CM"], [500, "D"], [400, "CD"],
            [100, "C"], [90, "XC"], [50, "L"], [40, "XL"],
            [10, "X"], [9, "IX"], [5, "V"], [4, "IV"], [1, "I"]
        ]),
        roman = [];
    for (let value of values) {
        let symbol = valueSymbols.get(value);
        while(num >= value){
            roman.push(symbol);
            num -= value;
        }
        if(!num) break;
    }
    return roman.join('');
};

// 字典法
var intToRoman = function(num) {
    const thousands = ["", "M", "MM", "MMM"];
    const hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
    const tens     = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
    const ones     = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];

    const roman = [];
    roman.push(thousands[Math.floor(num / 1000)]);
    roman.push(hundreds[Math.floor(num % 1000 / 100)]);
    roman.push(tens[Math.floor(num % 100 / 10)]);
    roman.push(ones[num % 10]);
    return roman.join('');
};
复制代码