近期一直在玩的游戏是汉诺塔，我倒是觉得这个游戏挺解乏的，但是我女票子却不喜欢，我让她玩 5 层，她讨价还价成 4 层，我再坚持一次，她就说不玩了不玩了，那就陪她玩 4 层咯。下面，我们来看看 js 制作的简单动画展示，这个游戏应该怎么玩。
继续阅读“汉诺塔游戏”Tag: 算法
工作中的一个问题之二
有一个二维数组如下：
let arr = [["a0", "a1"], ["a1", "a2"], ["a3"]];我们看到 a1 这个元素在数组的第 0 项和第 1 项都存在了，我们需要将其合并成一项：
// 需要转化成 [["a0", "a1", "a2"], ["a3"]]同理，针对一个任意项的二维数组，只要其中某单个元素重复了，就应该合并进同一个数组里，减少这个二维数组的个数。那么怎么实现这个呢？
继续阅读“工作中的一个问题之二”并查集的正确使用姿势
因为工作的关系，不得不学习了几种算法，好久不用又忘记了，这是一篇复习文章。
并查集回答的是连接问题，比如说从 a 城到 b 城有没有路，能回答有或者没有，但是不能回答具体的路是那几条，该怎么走；再比如说 a、z 这 2 个人能否通过共同好友的名片分享来加上微信。
并查集是解决点与点之间的关系，遇到实际问题的时候，需要我们进行转换成点与点，也就是建模。在数据结构上一般用数组来存储这些点。
继续阅读“并查集的正确使用姿势”检测无向图有没有闭环
这篇文章来自工作中的一个实际问题：电子工程师在进行电路设计时，一般不用画出有闭环的导线，否则就短路了，这个是没有意义的。为了避免电子工程师的误操作，需要做这么一个防呆的工作。这是一个实际的场景，为了解决这个问题，可以转换成一个图的问题。
先来解释几个概念。
继续阅读“检测无向图有没有闭环”最小生成树 kruskal 算法 js 实现
本站以前有一篇文章提到了 prim 算法的实现，具体点这里，我写了完整的示例，和优化版的 prim 在时间上的对比。现在我们来看另一种思路：Kruskal。
话不多说，先看实际效果和结论。在 1k 个节点里，lazy prim 耗时在 4s 左右，优化后的 prim 在 900ms 左右，而更高效的 Kruskal 在 600ms 左右。测试的前提条件是基于我的电脑硬件配置和 1k 个节点的完全稠密图。
要实现高效的 Kruskal 算法，需要基于高效的并查集数据结构，但是并查集我们不在这篇文章里谈及，我们主要谈谈 Kruskal 的思路。
继续阅读“最小生成树 kruskal 算法 js 实现”在 svg 中学习点到直线（线段）的最短距离算法
怎么计算点到直线的最短距离？学过数学的都会觉得这个话题不难，然而真正在编程中实操起来，还是有点不对劲的。你会觉得小时候，我的数学打过满分呐，现在这些知识却全都忘记了。 继续阅读“在 svg 中学习点到直线（线段）的最短距离算法”
一些排序算法
记得有一个明星程序员说，做一个 web developer 是不用学习数学的。那么自然也不用学习算法了。作为一个前端，在实际工作中确实很少实现什么排序算法，因为在 JavaScript 的语言层面，就已经实现 sort 函数了。但是学习这些排序算法，依然有助于我们理解这些语言相关内置函数的原理。 继续阅读“一些排序算法”
贪心算法 – JavaScript 描述
理解贪心算法的本质并不难，我们都很贪心。比如说，桌子上有 5 张人民币，面额分别是 100、50、20、10、5，但是按照要求我们只能选 3 张，那这 3 张怎么选呢？傻子都知道，我们肯定选面额大的。这就是贪心算法，每一步都是当下选择的最优解。
下面我们来看一些具体的问题。
动态规划（Dynamic programming）— JavaScript 描述
《数据结构与算法 JavaScript 描述》这本书错误好多，为什么译者不把这些错误纠正呢？
在工作中，我们都用过递归，用俗话说就是函数自己调用自己；而动态规划一般被认为是和递归相反的一种解决问题的思路：递归是从解决一个大问题开始，通过逐步解决一些小问题，来使最终的问题得到解决；动态规划的思路则恰恰相反。
继续阅读“动态规划（Dynamic programming）— JavaScript 描述”阿笠博士的兔子
这是公司 ctf 活动分值最高的一个题目，是这样说的：
柯南立刻想起阿笠博士培养出一对繁殖能力超强的兔子（雌雄），这种兔子嗅觉特别好，能快速找到丢失的镇馆之宝，这种兔子出生后一个月就会成年，成年的兔子再过一个月会生一对（雌雄）兔子，并且之后的每个月都会生一对兔子，兔子不会死亡，由于这种兔子一生只有一个伴侣，当兔子数量（对）越多对找回的镇馆之宝帮助最大，阿笠博士想知道当兔子数量（对）第11次出现素数之后过再128个月有多少对兔子，机智你能帮阿笠博士算出来吗？
当时应该没有人做出来，仔细分析一下，就是一个斐波那契数列加素数的判断，本身并不难。即便如此，我今晚也花了近三个小时在调试下面几行 js 代码。惭愧、惭愧，实在为自己的数学能力堪忧，还说要去考研······
继续阅读“阿笠博士的兔子”