FreeCodeCamp 中级算法题 - 罗马数字转换器

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

题目链接

问题解释

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

基本解法

思路提示

  • 这道题其实是有一点难度的,至少我在第一次尝试的时候花了些时间
  • 我们先来梳理一些基本概念,和逻辑思路。只有这些想清楚了,才能开始写代码
  • 首先,罗马数字通过以下几个字母来表示:
数字 字符
1 I
5 V
10 X
50 L
100 C
500 D
1000 M
  • 我们可以先通过罗马数字转数字的逻辑来反推这道题目的解题思路,转换时,对于相邻的字母,如果左边比右边大就相加,右边比左边大就相减
    • 比如,"CX" 表示 110,而 "XC" 表示 90
  • 现在,我们至少可以有一条基本思路。对于给定的数字,只需要按照上面的对应关系从大到小进行比较,匹配到了(小于等于)就得出罗马数字字符,然后原数减去匹配数字,再继续匹配就可以了
    • 举个例子,给出数字为 100,它小于 1000500。比较到 100 发现它们相等,因此得出 C
    • 如果给出 120,还是先获取到 "C",然后减去 100 得到 20。那么 20 根据上面的对应关系匹配到 10,因此得到 "X"。再减去 10,也是匹配到 "X"。因此,结果是 "CXX"
  • 下一步,就是考虑一些特殊情况,这里有一个很重要的原则:同一罗马数字字符,最多连续出现三次。引申出一条原则:如果右边比左边大,那么左边只可以有一位数
    • 听起来好像很复杂,来看例子。对于 4,不能转换成 "IIII",而应为 "IV"
    • 对于 8,不可以转换成 "IIX",而应为 "VIII"
  • 进一步考虑,我们会发现,其实特殊情况就是罗马字符相减,或者说左边比右边小的情况。比如对于 8,转换逻辑与上面提到的基本思路是完全相符的。但 9 是不符合的,因为按照一开始的思路,9 会被转换成 "VIIII"这条结论十分重要,如果没看懂,请再读一遍。特殊情况列表如下:
数字 字符
4 IV
9 IX
40 XL
90 XC
400 CD
900 CM
  • 这时候你可能会有疑问,为什么 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 处于遍历数组的过程中,作用是判断特殊值。如果你不明白上面的这个写法,请你和我一样,列出来这样的一个表格:
当前元素 索引(index) 特殊值 特殊值计算方式 特殊值计算索引
1000 6
500 5 900 1000 - 100 6, 4
100 4 400 500 - 100 5, 4
50 3 90 100 - 10 4, 2
10 2 40 50 - 10 3, 2
5 1 9 10 - 1 2, 0
1 0 4 5 - 1 1, 0
  • 仔细看第二列,也就是当前索引与最后一列的关系。设当前索引为 i,那么最后一列要么是 (i + 1), (i),要么是 (i + 1), (i - 1)
  • 进一步观察可以发现,除了索引为 6 的情况,其他情况都符合:当索引 i 为奇数时最后一列是 (i + 1), (i - 1),当索引为偶数时最后一列是 (i + 1), (i)
  • 代码中的 checkerIndex 就是表格的最后一列,特殊值计算索引;checkerNum 就是求差之后的特殊值,也就是表格的第三列。需要注意的是,元素 1000 没有特殊值需要检查,因此我们要加上 i < 6 的判断
  • 这个解法可以算是暴力解法了。但能做的优化我还是尽力做了的。比如,不需要每次都判断所有的特殊值,而是动态地生成特殊值,只检查当前情况下的特殊值
  • 这个解法,效率一定是不高的,时间复杂度达到了 n 平方。只是这个解法不需要太多的技巧,相信只要你理解了一开始说的思路,知道要做特殊情况判断,写出来这个答案还是不成问题的

优化 - 优化初始值定义

思路提示

  • 既然判断特殊值这么麻烦,而且特殊值也就那几个,为什么不把它们也写进数组中呢?比如特殊值 40,我们完全可以把它定义在 1050 之间,因为这个 40 是数字小于 50 并且大于 10 的时候需要判断的,那我们在 10 之前先判断就好了
  • 有的朋友可能会想到,为什么不用 Object 去定义呢?这样就不用定义两个数组了。但请注意,对象存储的是一一对应关系,而不是顺序。JavaScript 中遍历对象的方法你肯定知道,那就是 for...in,即使是 ES6 的 for...of 也不能保证按”顺序”输出对象中的元素,因为,Object 本身就不存在顺序的概念
  • 而遍历数组,我们可以用 forwhile.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 = 310 的对应字符串 "X"
  • 接下来考虑特殊情况,按照上一条的思路考虑
    • 对于 40 来说,输出的就会是 "XXXX",当然这个结果不是我们想要的。因此,我们需要把前三个或后三个 "X" 去掉,并在结尾补上更高一级的 "L"
    • 比如 90 不应为 "LXXXX",而应该是 "XC"。在这种情况下,显然我们要去掉的是前四个 "LXXX"
    • 再比如,4 不应为 "IIII""IV",所以我们要去掉前三个 "I"
  • 综上所述,遇到特殊值,我们处理的方式就是:保留最后一个罗马字符,并在后面添加更高级的罗马字符
  • 以下代码,我用到了递归写法,供大家参考。由于是递归调用,不仅需要遍历过程中当前的元素和索引,还需要当前已生成的罗马字符。当然,如果你愿意,也可以把这个结果存到函数外部。只是我个人更喜欢写到参数里面去
  • 就算不用递归,一样是可以写成的,请大家尝试一下

参考链接

伪代码(逻辑思路)

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, "");
}

解释

  • 要解释的,都在上面的伪代码和代码注释中。如果你有哪里不明白的,或者有更好的建议,请在下方评论留言
  • 如果你觉得我写的方法漏洞很大,或者有很明显的优化空间,也请在下方评论指出,不胜感激
文章目录
  1. 1. 罗马数字转换器 (Roman Numeral Converter)
    1. 1.1. 题目链接
    2. 1.2. 问题解释
  2. 2. 基本解法
    1. 2.1. 思路提示
    2. 2.2. 参考链接
    3. 2.3. 伪代码(逻辑思路)
    4. 2.4. 代码
    5. 2.5. 解释
  3. 3. 优化 - 优化初始值定义
    1. 3.1. 思路提示
    2. 3.2. 代码
    3. 3.3. 解释
  4. 4. 优化 - 封装函数
    1. 4.1. 思路提示
    2. 4.2. 参考链接
    3. 4.3. 伪代码(逻辑思路)
    4. 4.4. 代码
    5. 4.5. 解释
,