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

比如，2 用 II 表示，即 1+1。12 用 XII 表示，即 10+2。27 用 XXVII 表示，即 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;
};