LeetCode 12. Integer to Roman

发布于: 2020 年 07 月 08 日
LeetCode 12. Integer to Roman

问题描述

罗马数字用 7 个字符表示,I, V, X, L, C, D。它们与数字的对应关系如下:

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

比如,2II 表示,即 1+112XII 表示,即 10+227XXVII 表示,即 2*10+5+2

通常,在罗马数字的书写中,数字从左到右,越来越小。但是,4 并不是用 IIII 表示,而是用 IV,因为 5-1=4。同样,对于 9,用 IX 表示。有如下 6 种符号可在减法中使用:

  • I 可放在 V (5) 和 X (10) 的前面,表示 4 和 9。

  • X 可放在 L (50) 和 C (100) 的前面,表示 40 和 90。

  • C 可放在 D (500) 和 M (100) 的前面,表示 400 和 900。

现在给定一个整数,将它转换成罗马数字。假定输入数字的范围在 [1, 3999]

栗 1:

输入:3
输出:"III"

栗 2:

输入:4
输出:"IV"

栗 3:

输入:9
输出:"IX"

栗 4:

输入:58
输出:"LVIII"
解释:
50 + 5 + 3

栗 5:

输入:1994
输出:"MCMXCIV"
解释:
1000 + 900 + 90 + 4

想看英文描述的戳这里。

解题思路

题目挺简单的,因为罗马数字所能表示的值也就那么固定的几种,1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 100

我们只需要将数字分解为它所能表示的值的组合,然后根据数字与罗马字符的映射关系,拼接结果。

如何将数字分解?从大到小遍历可表示的值,若遇到小于等于数字的值,则代表该值为数字组合的一部分,减去该值,继续遍历。

js 代码如下:

var intToRoman = function (num) {
// 保存结果字符串
let roman = "";
const numArray = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
const romanArray = [
"M",
"CM",
"D",
"CD",
"C",
"XC",
"L",
"XL",
"X",
"IX",
"V",
"IV",
"I",
];
let i = 0;
while (i < numArray.length) {
const key = numArray[i];
if (num === 0) {
break
}
if (num >= key) {
const count = Math.floor(num / key);
// 取对应罗马符号
const romanSymbol = romanArray[i];
// 拼接符号
let j = 0;
while (j < count) {
roman += romanSymbol;
j += 1;
}
// 减去已计算的数
num -= key * count;
}
i += 1;
}
return roman;
};

发布于: 2020 年 07 月 08 日 阅读数: 4
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 12. Integer to Roman