罗马数字转换器 (Roman Numeral Converter)

题目链接

• 中文链接
• 英文链接
• 级别：中级 (Intermediate Algorithm Scripting)

问题解释

• 这个 function 接收一个数字参数 num。返回值为转换罗马数字字符串
• 比如接收的是 2，那么输出就是 "II"。如果接受的是 12，那么输出就是 "XII"

基本解法

思路提示

• 这道题其实是有一点难度的，至少我在第一次尝试的时候花了些时间
• 我们先来梳理一些基本概念，和逻辑思路。只有这些想清楚了，才能开始写代码
• 首先，罗马数字通过以下几个字母来表示：

• 我们可以先通过罗马数字转数字的逻辑来反推这道题目的解题思路，转换时，对于相邻的字母，如果左边比右边大就相加，右边比左边大就相减
  • 比如，"CX" 表示 110，而 "XC" 表示 90
• 现在，我们至少可以有一条基本思路。对于给定的数字，只需要按照上面的对应关系从大到小进行比较，匹配到了(小于等于)就得出罗马数字字符，然后原数减去匹配数字，再继续匹配就可以了
  • 举个例子，给出数字为 100，它小于 1000 和 500。比较到 100 发现它们相等，因此得出 C
  • 如果给出 120，还是先获取到 "C"，然后减去 100 得到 20。那么 20 根据上面的对应关系匹配到 10，因此得到 "X"。再减去 10，也是匹配到 "X"。因此，结果是 "CXX"
• 下一步，就是考虑一些特殊情况，这里有一个很重要的原则：同一罗马数字字符，最多连续出现三次。引申出一条原则：如果右边比左边大，那么左边只可以有一位数
  • 听起来好像很复杂，来看例子。对于 4，不能转换成 "IIII"，而应为 "IV"
  • 对于 8，不可以转换成 "IIX"，而应为 "VIII"
• 进一步考虑，我们会发现，其实特殊情况就是罗马字符相减，或者说左边比右边小的情况。比如对于 8，转换逻辑与上面提到的基本思路是完全相符的。但 9 是不符合的，因为按照一开始的思路，9 会被转换成 "VIIII"。这条结论十分重要，如果没看懂，请再读一遍。特殊情况列表如下：

• 这时候你可能会有疑问，为什么 99 不算特殊情况？这就涉及到另一条规则，如果左边比右边小，那么左右两个罗马数字字符只可以跨一位。意思是，比如对于 "I"，可以有 "IV" 和 "IX"，但不会有 "IC"
  • 对于 99，转换思路是，先转换 90，得到 "XC"。再转换 9，得到 "IX"。因此结果是 "XCIX"，而不是 "IC"。这个结论，是解决这道题目的关键
  • 同理，对于 999，也应该是先转换 900，再转换 90，再转换 9
• 以上就是转换的基本思路。剩下的就是写代码了

参考链接

• 罗马数字 维基百科页面
• 除此之外，不需要其他参考，只要你会写循环、会四则运算就行

伪代码(逻辑思路)

• 由于这道题代码看起来会比较复杂，因此先给出伪代码。如果你已经理解了上面的思路，那么你可以参考以下的逻辑思路，来试着自己写一下
• 整体上，我们才用 num 来进行循环。只要找到对应的罗马字符，我们就把 num 缩小，同时把对应的罗马字符添加到结果。显然，循环的跳出条件就是 num === 0
• 如果你在写的过程中遇到问题，请通过在代码中加上 console.log 来调试，或者再回顾一下上面的思路详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 生成一个用于判断的数组，[1, 5, 10, 50, 100, 500, 1000]
# 生成一个数组，元素为以上数组元素的罗马字符对应值
# 生成一个空字符串，用于储存结果

当 num > 0 时:
    从右开始遍历数组:
        如果 num 大于等于数组中的当前元素:
            根据索引，生成需要判断的特殊值(比如这时候元素是50，那就要生成 90)
            如果 num 大于等于这个特殊值:
                给结果添加上特殊值的对应的罗马字符(比如 90 就添加 XC)
                num 减去这个特殊值，用于下次循环判断
            否则:
                直接把这个匹配到的元素转换成对应的罗马字符
                num 减去这个元素，用于下次循环判断
        否则:
            继续遍历数组


两层循环结束，返回结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

function convert(num) {
    var numArr = [1, 5, 10, 50, 100, 500, 1000];
    var strArr = ["I", "V", "X", "L", "C", "D", "M"];
    var result = "";

    while (num > 0) {
        var i = numArr.length;

        while (i >= 0) {
            if (num >= numArr[i]) {
                // 如果你看不懂这部分，先举几个例子来试试
                // 详情请看底下的解释
                var checkerIndex = [i + 1, i % 2 ? i - 1 : i];
                var checkerNum = numArr[checkerIndex[0]] - numArr[checkerIndex[1]];

                if (i < 6 && num >= checkerNum ) {
                    result += strArr[checkerIndex[1]] + strArr[checkerIndex[0]];
                    num -= checkerNum;
                } else {
                    result += strArr[i];
                    num -= numArr[i];
                }
            } else {
                i--;
            }
        }
    }

    return result;
}

解释

• 再回顾一遍整体思路：
  • 以 num > 0 为跳出条件进行循环
  • 对于 num，通过 numArr 来逐个判断。如果大于当前元素，就表示匹配到，可以进行转换了
  • 进一步判断特殊值，如果是特殊值，就按照特殊值方式转换，否则就按标准思路转换
• 其实，唯一需要解释的就是 [i + 1, i % 2 ? i - 1 : i] 那里吧。我们先看看它所在的 if 区域是干什么的
• 这个 if 处于遍历数组的过程中，作用是判断特殊值。如果你不明白上面的这个写法，请你和我一样，列出来这样的一个表格：

• 仔细看第二列，也就是当前索引与最后一列的关系。设当前索引为 i，那么最后一列要么是 (i + 1), (i)，要么是 (i + 1), (i - 1)
• 进一步观察可以发现，除了索引为 6 的情况，其他情况都符合：当索引 i 为奇数时最后一列是 (i + 1), (i - 1)，当索引为偶数时最后一列是 (i + 1), (i)
• 代码中的 checkerIndex 就是表格的最后一列，特殊值计算索引；checkerNum 就是求差之后的特殊值，也就是表格的第三列。需要注意的是，元素 1000 没有特殊值需要检查，因此我们要加上 i < 6 的判断
• 这个解法可以算是暴力解法了。但能做的优化我还是尽力做了的。比如，不需要每次都判断所有的特殊值，而是动态地生成特殊值，只检查当前情况下的特殊值
• 这个解法，效率一定是不高的，时间复杂度达到了 n 平方。只是这个解法不需要太多的技巧，相信只要你理解了一开始说的思路，知道要做特殊情况判断，写出来这个答案还是不成问题的

优化 - 优化初始值定义

思路提示

• 既然判断特殊值这么麻烦，而且特殊值也就那几个，为什么不把它们也写进数组中呢？比如特殊值 40，我们完全可以把它定义在 10 与 50 之间，因为这个 40 是数字小于 50 并且大于 10 的时候需要判断的，那我们在 10 之前先判断就好了
• 有的朋友可能会想到，为什么不用 Object 去定义呢？这样就不用定义两个数组了。但请注意，对象存储的是一一对应关系，而不是顺序。JavaScript 中遍历对象的方法你肯定知道，那就是 for...in，即使是 ES6 的 for...of 也不能保证按”顺序”输出对象中的元素，因为，Object 本身就不存在顺序的概念
• 而遍历数组，我们可以用 for、while、.forEach() 或者 for...of。这些一定是按照一定顺序的。所以还是得用两个数组，然后通过索引来建立对应关系
• 有朋友可能会说，”我用 Object，测试通过了噢”，”为什么不能用？在浏览器控制台中也是按’顺序’输出的”。那我们进一步展开来讲。如果对象的 key 是唯一类型的，那么确实，for...of 会按定义的顺序输出。如果对象的 key 是包含多种类型的(比如数字和字符串)，而且定义的顺序也是混的，那么输出就不一定会按照原来的顺序了
• 这道题目中，显然我们的 key 只有数字(注意，用数字作为对象的 key，会被自动转换为字符串，你可以试试)，之所以我不打算才用对象来写，就是防止产生 “对象是有顺序的” 这样的误会

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function convert(num) {
    var numArr = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000];
    var strArr = ["I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"];
    var result = "";

    while (num > 0) {
        var i = numArr.length;

        while (i >= 0) {
            if (num >= numArr[i]) {
                result += strArr[i];
                num -= numArr[i];
            } else {
                i--;
            }
        }
    }

    return result;
}

解释

• 思路还是跟之前的一样，没有任何性能方面的优化，但至少不用去写复杂的逻辑判断了

优化 - 封装函数

思路提示

• 说到封装，还记得 “DRY” 原则么？请查看上一片博文，里面提到过
• 先来看看，需不需要封装。举个例子，对于 30 这样的数，我们需要进行 3 次判断、添加字符串和减去 10 这样的重复操作
• 进一步思考，对于任何需要转换的数，我们都需要进行判断、添加字符串和减去特定值的操作。因此，由于存在这样的重复操作，至少封装是可以进行的
• 既然决定要封装，那么下一步就要定好传入的参数和返回值。既然原先的输入是数字，我们最终要输出字符串，很显然，封装好的参数也应该是这样：输入数字，输出字符串
• 继续考虑，我们可以举一个例子。比如传入的是 30，那我们应该输出 "XXX"。按照原先的思路，30 是在遍历中匹配 10 的。因此，这里我们不难推导出输出就是重复 30 / 10 = 3 次 10 的对应字符串 "X"
• 接下来考虑特殊情况，按照上一条的思路考虑
  • 对于 40 来说，输出的就会是 "XXXX"，当然这个结果不是我们想要的。因此，我们需要把前三个或后三个 "X" 去掉，并在结尾补上更高一级的 "L"
  • 比如 90 不应为 "LXXXX"，而应该是 "XC"。在这种情况下，显然我们要去掉的是前四个 "LXXX"
  • 再比如，4 不应为 "IIII" 是 "IV"，所以我们要去掉前三个 "I"
• 综上所述，遇到特殊值，我们处理的方式就是：保留最后一个罗马字符，并在后面添加更高级的罗马字符
• 以下代码，我用到了递归写法，供大家参考。由于是递归调用，不仅需要遍历过程中当前的元素和索引，还需要当前已生成的罗马字符。当然，如果你愿意，也可以把这个结果存到函数外部。只是我个人更喜欢写到参数里面去
• 就算不用递归，一样是可以写成的，请大家尝试一下

参考链接

• String.repeat()

伪代码(逻辑思路)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 初始化不含特殊条件的数字数组与罗马字符对应数组
# 封装好的 function，参数为当前遍历中的元素 num，元素的索引 i 以及目前已生成的罗马字符 str
# function 内部逻辑如下

如果 num 为 0 或 i < 0，则应该跳出并返回 str

如果 num 大于等于当前元素:
    如果当前数字符合 4，9，40 等特殊值:
        递归回调，num 减去特殊值，i 减 1 判断下一个元素，罗马字符为左小右大
    如果不为特殊值，暂存下来当前的结果，即重复 `num / 当前元素` 次当前数对应的罗马字符

    如果当前结果长度大于 3:
        递归回调，num 减去当前元素的重复次数倍，i 减 1 判断下一个元素，第三个参数为当前结果保留最后一个字符，并添加数组中的下一个字符，即第 `i + 1` 个字符
    否则:
        递归回调，前两个参数与上面相同，但第三个参数在 str 基础上直接加当前结果
    
如果 num 小于当前元素:
    i 减 1，继续循环判断

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

function convert(num) {
    var numArr = [1, 5, 10, 50, 100, 500, 1000];
    var strArr = ["I", "V", "X", "L", "C", "D", "M"];

    // 递归辅助函数
    function helper(num, i, str) {
        // 边界及跳出条件
        if (num === 0 || i < 0) {
            return str;
        }

        // 暂时生成的罗马字符
        var temp = "";

        if (num >= numArr[i]) {
            // 这里与上一个方法一致
            var checkerIndex = [i + 1, i % 2 ? i - 1 : i];
            var checkerValue = numArr[checkerIndex[0]] - numArr[checkerIndex[1]];
            // 暂存差值
            var tempDiff = Math.floor(num / numArr[i]) * numArr[i];

            // 特殊情况判断。如果 num 与特殊值的第一位相同，那就证明遇到了特殊情况
            if (num.toString()[0] === checkerValue.toString()[0]) {
                // 直接减掉特殊值，罗马字符则为左小右大，与上一个方法思路一致
                return str + helper(num - checkerValue, i - 1, strArr[checkerIndex[1]] + strArr[checkerIndex[0]])
            }

            // 如果不是特殊情况，字符重复输出 `num / numArr[i]` 次
            temp += strArr[i].repeat(Math.floor(num / numArr[i]));

            // 特殊情况，即连续出现三次以上相同字符
            if (temp.length > 3) {
                // 此时字符串应取最后一位，并把后一个元素加进来
                return helper(num - tempDiff, i - 1, str + temp.slice(-1) + strArr[i + 1]);
            } else {
                return helper(num - tempDiff, i - 1, str + temp);
            }
        } else {
            // 否则，当前元素太大，索引减一继续判断，str 不变
            return helper(num, i - 1, str);
        }
    }

    // 初始调用，字符串为 0，从 numArr 的最后一个元素开始判断
    return helper(num, numArr.length - 1, "");
}

解释

• 要解释的，都在上面的伪代码和代码注释中。如果你有哪里不明白的，或者有更好的建议，请在下方评论留言
• 如果你觉得我写的方法漏洞很大，或者有很明显的优化空间，也请在下方评论指出，不胜感激