LeetCode 12. Integer to Roman

用户头像
liu_liu
关注
发布于: 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 日 阅读数: 22
用户头像

liu_liu

关注

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

还未添加个人简介

评论

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