标签：算法

因为工作的关系，不得不学习了几种算法，好久不用又忘记了，这是一篇复习文章。

并查集回答的是连接问题，比如说从 a 城到 b 城有没有路，能回答有或者没有，但是不能回答具体的路是那几条，该怎么走；再比如说 a、z 这 2 个人能否通过共同好友的名片分享来加上微信。

并查集是解决点与点之间的关系，遇到实际问题的时候，需要我们进行转换成点与点，也就是建模。在数据结构上一般用数组来存储这些点。

继续阅读“并查集的正确使用姿势”

本站以前有一篇文章提到了 prim 算法的实现，具体点这里，我写了完整的示例，和优化版的 prim 在时间上的对比。现在我们来看另一种思路：Kruskal。

话不多说，先看实际效果和结论。在 1k 个节点里，lazy prim 耗时在 4s 左右，优化后的 prim 在 900ms 左右，而更高效的 Kruskal 在 600ms 左右。测试的前提条件是基于我的电脑硬件配置和 1k 个节点的完全稠密图。

要实现高效的 Kruskal 算法，需要基于高效的并查集数据结构，但是并查集我们不在这篇文章里谈及，我们主要谈谈 Kruskal 的思路。

继续阅读“最小生成树 kruskal 算法 js 实现”

这是公司 ctf 活动分值最高的一个题目，是这样说的：

柯南立刻想起阿笠博士培养出一对繁殖能力超强的兔子（雌雄），这种兔子嗅觉特别好，能快速找到丢失的镇馆之宝，这种兔子出生后一个月就会成年，成年的兔子再过一个月会生一对（雌雄）兔子，并且之后的每个月都会生一对兔子，兔子不会死亡，由于这种兔子一生只有一个伴侣，当兔子数量（对）越多对找回的镇馆之宝帮助最大，阿笠博士想知道当兔子数量（对）第11次出现素数之后过再128个月有多少对兔子，机智你能帮阿笠博士算出来吗？

当时应该没有人做出来，仔细分析一下，就是一个斐波那契数列加素数的判断，本身并不难。即便如此，我今晚也花了近三个小时在调试下面几行 js 代码。惭愧、惭愧，实在为自己的数学能力堪忧，还说要去考研······

继续阅读“阿笠博士的兔子”