昨日，在 FCC 平台整整用了两三小时，才刷出一道 JS 算法题，回首而看，最终的代码也就那么多行，记录过程，写文以促进之后改进，也顺便整理一下自己在 FCC 上遇到问题后的解决思路。
想看答案的可以直接拉至文章后方~~
数字转换规则
罗马数字我们都不陌生，I、II、V 、IX 等字符见文知意，可是当阿拉伯数字达到百千级别的时候，用什么字母表示？字母的排列顺序又应该是什么样子的呢？下面诺列了几个规则：
基本字符
I、V、X、L、C、D、M
分别代表
1、5、10、50、100、500、1000
计数规则：
- 若干相同数字连写表示的数是这些罗马数字的和，如III=3；
- 小数字在大数字前面表示的数是用大数字减去小数字，如IV＝4；
- 小数字在大数字后面表示的数是用大数字加上小数字，如VI=6;
组合规则：
- 基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
- 不能把基本数字 V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
- V 和 X 左边的小数字只能用 Ⅰ。
- L 和 C 左边的小数字只能用 X。
- D 和 M 左 边的小数字只能用 C 。
可见该字符只适用于 4000 以下的正整数阿拉伯数字。
思路历程
按照规则来说，看来也就是要满足类似如下输入和输出：
首先想到的是找不同字符：最终也就只有 I、V、X、L、C、D、M 这七个字符分别代表几个数字，进行一定的左右顺序排列后完成转换。那么在这里首先要生成一个装有七个元素的数组，这时输入 9 的话，去拼装 I 和 X，输入 97 的话，去拼装 L 或者 C 等等。
var Roman = {
1: 'I',
5: 'V',
10: 'X',
50: 'L',
100: 'C',
500: 'D',
1000: 'M'
};
就像 97 ，选择从 L (50)向右拼装呢还是选择 C (100)向左拼装，看来要去找输入数字左右两侧有对应罗马字符的数字，例如 97 的左边有代表 'L' 的 50 ，右边有代表 'C' 的 100。
开始设计算法，处处断点跟踪。
function convert(num) {
if (isNaN(num)) return num;
var str = "";
var left, right; // 找到输入数字的左值和右值
var p;
for (p in Roman) {
if (num > p) {
left = p; // 左边的值一直在跟踪
} else {
right = p; // 知道左边的值找到后，左边的值得下一个赋给右边的值
break;
}
}
console.log("(left: " + left + ")----" + num + "----(right: " + right + ")");
return str;
}
断点跟踪情况来看。发现确实能找到输入数字左右两边的值。
变得更复杂了，及时收手，重新思考
哇塞，找到输入数字左右两个数字后呢？在之前的转换规则里有说过，最大的罗马数字(例如‘V’)，左侧的数字(例如‘I’)代表减少，右侧的数字代表(例如‘II’)增加。这时，罗马数字‘IV’、‘VII’即为阿拉伯数字 4 和 7 了。
当这时只用单个字符左右拼装 3999 的时候，一切都复杂了。
3999 --> MMMCMXCIX
要判断 9 应该转换为 VIIII 还是 IX ，必然会多出很多选择循环分支，变得更复杂了，及时收手，重新查找规律。
原来，像 97 这样的数字，不必纠结于是从 L(50) 开始拼装还是从 C(100) 开始拼装，90 转换成 XC ，7 转换成 VII 即可。看了看别的数字，都是这个规律呢，于是制定出如下对应表，直接查找到 个十百千 的任何一个。
var Roman = [["","I","II","III","IV","V","VI","VII","VIII","IX"],
["","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"],
["","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"],
["","M","MM","MMM"," "," "," "," "," "," "]];
3999 就可以理解为：3000 -> MMM, 900 -> CM, 90 -> XC, 9 -> IX 了。
3999 --> MMMCMXCIX
最终算法实现
其实你只用从这里正式看就可以了，前面的情景铺设不利于直接解答你的困惑呢。最终实现功能的函数才只有短短的 8 行。
- ReverseArr 数组用来将输入数字转换成字符数组后倒序保存，这样 ReverseArr[0] 永远是输入数字的个位数，便于处理。
- CorrectArr 数组用来将每个 ReverseArr 数组的数字查表转换成对应的罗马数字。
- 最终返回 CorrectArr 数组经过 join 方法后连接起来的字符串。
var Roman = [["","I","II","III","IV","V","VI","VII","VIII","IX"],
["","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"],
["","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"],
["","M","MM","MMM"," "," "," "," "," "," "]];
// 只能转换 4000 以下的正整数阿拉伯数字
function convert(num) {
if(isNaN(num)) return num;
var ReverseArr = num.toString().split("").reverse();
var CorrectArr = [];
for (var i = 0; i < ReverseArr.length; i++) {
CorrectArr.unshift(Roman[i][ReverseArr[i]]);
}
return CorrectArr.join("");
}
俩小时后的这一瞬间，感动死我了思密达：
�整理自己的思考过程
- 查看 MDN 文档(重要)，MDN 文档由网上所有人参与编辑维护，里面有几乎全部的 JS 对象及其方法的使用用例。
- 随时 Chrome 开发者工具测试 demo 和调试，处处 console.log “人肉”看状态。
- 搜索引擎 -- 百度 or 谷歌(辅助)，算法这块，到瓶颈之处真不好意思一直不查资料想下去。
- FCC 微信群，记得“提问的智慧”哦，人人都很忙呢。
- Hello，我是韩亦乐，现任本科软工男一枚。软件工程专业的一路学习中，我有很多感悟，也享受持续分享的过程。如果想了解更多或能及时收到我的最新文章，欢迎订阅我的个人微信号：韩亦乐。我的简书个人主页中，有我的订阅号二维码和 Github 主页地址；我的知乎主页 中也会坚持产出，欢迎关注。
- 本文内部编号经由我的 Github 相关仓库统一管理；本文可能发布在多个平台但仅在上述仓库中长期维护；本文同时采用【知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议】进行许可。
