整数转罗马数字（12）

题目

罗马数字包含以下七种字符： 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 到 3999 的范围内。

示例

输入: 3 输出: "III"

输入: 4 输出: "IV"

输入: 9 输出: "IX"

输入: 58 输出: "LVIII"

解释: L = 50, V = 5, III = 3.

输入: 1994 输出: "MCMXCIV"

解释: M = 1000, CM = 900, XC = 90, IV = 4.

算法

暴力法

需要考虑的情况有：

• 位数
• 当前位上的数字是不是4或9
• 当前位上的数字是不是5
• 因为题目限制了最大为3999，且以上情况不需考虑千分位，所以千分位也单独判断

我们使用变量maxDig存储当前的位数，从最高位开始向低位循环：

• 使用(数字 % 10^位数) / 10^(位数-1)来获取当前位上的数字
• 我们根据当前位上的数字是不是等于4、9或者大于小于5，加上当前的位数来判断对应的罗马字母

export const intToRoman = (num) => {
	let maxDig = num.toString().length;
	let roman = "";
	for (; maxDig > 0; maxDig--) {
		let curCount = ~~((num % 10 ** maxDig) / 10 ** (maxDig - 1));
		if (maxDig === 4) {
			roman += "M".repeat(curCount);
		} else {
			if (curCount === 9) {
				if (maxDig === 3) roman += "CM";
				else if (maxDig === 2) roman += "XC";
				else if (maxDig === 1) roman += "IX";
			} else if (curCount === 4) {
				if (maxDig === 3) roman += "CD";
				else if (maxDig === 2) roman += "XL";
				else if (maxDig === 1) roman += "IV";
			} else if (curCount < 4) {
				if (maxDig === 3) roman += "C".repeat(curCount);
				else if (maxDig === 2) roman += "X".repeat(curCount);
				else if (maxDig === 1) roman += "I".repeat(curCount);
			} else {
				if (maxDig === 3) roman += "D" + "C".repeat(curCount - 5);
				else if (maxDig === 2) roman += "L" + "X".repeat(curCount - 5);
				else if (maxDig === 1) roman += "V" + "I".repeat(curCount - 5);
			}
		}
	}
	return roman;
};

另一种暴力法

按每一位上的数字获取对应的罗马字母

export const intToRoman = (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"];
	return thousands[~~(num / 1000)] + hundreds[~~((num % 1000) / 100)] + tens[~~((num % 100) / 10)] + ones[~~(num % 10)];
};

贪心

我们尽可能地贪心的使用一个尽可能大的且不大于数字num的罗马数字来表示num

当我们每使用一个尽可能大且不大于这个数字的罗马字母表示这个数字后，我们从这个数字中减去这个尽可能大的数，然后继续判断

export const intToRoman = (num) => {
	const numbers = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
	const symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
	let roman = "";
	for (let i = 0; i < numbers.length && num >= 0; i++) {
		while (numbers[i] <= num) {
			num -= numbers[i];
			roman += symbols[i];
		}
	}
	return roman;
};