并查集的正确使用姿势

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

并查集回答的是连接问题,比如说从 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 张怎么选呢?傻子都知道,我们肯定选面额大的。这就是贪心算法,每一步都是当下选择的最优解。

下面我们来看一些具体的问题。

继续阅读“贪心算法 – JavaScript 描述”

动态规划(Dynamic programming)— JavaScript 描述

《数据结构与算法 JavaScript 描述》这本书错误好多,为什么译者不把这些错误纠正呢?

在工作中,我们都用过递归,用俗话说就是函数自己调用自己;而动态规划一般被认为是和递归相反的一种解决问题的思路:递归是从解决一个大问题开始,通过逐步解决一些小问题,来使最终的问题得到解决;动态规划的思路则恰恰相反。 继续阅读“动态规划(Dynamic programming)— JavaScript 描述”

阿笠博士的兔子

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

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

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

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

金钱正是有史以来最普遍也最有效的互信系统

这个月缺失两天

金钱正是有史以来最普遍也最有效的互信系统
金钱正是有史以来最普遍也最有效的互信系统

2018-02-28

Script Error 收集了很多 JavaScript 错误的类型是 “Script Error” ,为什么呢?可以查看這個鏈接:https://blog.sentry.io/2016/05/17/what-is-script-error

内容来自曾小乱的blog:https://zengxiaoluan.com/2018/02/27/what-i-know-about-js-error-collection/?wx 继续阅读“金钱正是有史以来最普遍也最有效的互信系统”

水塘抽样算法和Fisher–Yates算法

水塘抽样算法

公司尾牙的抽奖程序,我代码已经写好了。给公司的一些总工看了一下核心的抽奖代码,其中一个总工提出了“水塘抽样”算法来解决随机性和公平性的问题,所以就有了这篇博客。 继续阅读“水塘抽样算法和Fisher–Yates算法”