LeetCode 12. Integer to Roman

关注

发布于: 2020 年 07 月 08 日

问题描述﻿
罗马数字用 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;
};
﻿

发布于: 2020 年 07 月 08 日阅读数: 42

原文链接:【http://xie.infoq.cn/article/f28c8b85b9508127b1a8488bd】。文章转载请联系作者。

liu_liu

关注

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

还未添加个人简介

发布

暂无评论

创作场景

LeetCode 12. Integer to Roman

问题描述

解题思路

liu_liu

评论