Yinode Blog

Wubba lubba dub dub

计算π [蒙特卡洛+碰撞计数+巴塞尔]

仅供娱乐 蒙特卡洛方法 基于统计的方法 发射大量的随机点,通过这个比值就能换算出π的值 至于判断点是否在圆内用简单的通项公式 sqrt((a - x) ^ 2 + (b - y) ^ 2) <=

计算传递闭包 [离散数学]

传递闭包 传递闭包、即在数学中,在集合 X 上的二元关系 R 的传递闭包是包含 R 的 X 上的最小的传递关系。 例如,如果 X 是(生或死)人的集合而 R 是关系“为

生成排列与组合 [离散数学]

前置工具代码 一些前置的工具 下面代码不会再给出 // 求N的阶乘 const factorial = (() => { var f = [1, 1] var i = 2 return function factorial(n) { if (typeof f[n] != 'undefined') return f[n] var result = f[i - 1] for (; i <= n; i++) f[i] = result =

A Star 搜索算法 常用于游戏中的路径查找

非常酷的一个启发式搜索算法,整体类似于dij最短路径算法,只不过加入了预估距离的概念,当然由于博客数据丢失,之前的博客内容没了,不过还好代码

连连看中的广度优先搜索算法

由于博客数据丢失,只剩下了代码。。。。。之前写的MD都没了。。 const gameConfig = { maxLevel: 10// 最大搜索层级 2代表 只搜索经过两次转角能到达的点 } // 简易队列系统 配合

编辑距离算法 - 计算两个单词之间的相似度

利用简单的编辑距离,来判断两个拉丁文单词直接的相似度,常用于输入纠错!

LRU 缓存算法

LRU 是一种 『最久未用优先淘汰』 的缓存管理算法

机器学习 K均值分类算法

基础且典型的一种无监督机器学习分类算法

哈希表的实现

哈希表 散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数

最长递增子序列 与 0 1 背包问题 [动态规划]

最长递增子序列 在计算机科学中,最长递增子序列(longest increasing subsequence)问题是指,在一个给定的数值序列中,找到一个子序列,使得

JavaScript 中 几种快排的实现

其实也就是前段时间点阮一峰快排事件,正好去看看大家的实现,在这里记录一下,并写一下注释 实现 1 特点 简单 智力经济 性能较差 加随机化比较方便 只要把取

算法实战 文本校对工具 最长公共子序列

前段时间公司里有需求需要一个文本对比工具,我在网上也收集到了一些资料,找到了一些对比 DEMO,仔细考虑之后恍然大悟,这东西不就是最长公共子序

最小硬币问题 [动态规划]

问题 假设你当前拥有 3 元 6 元 7 元的硬币 数量为无限。问 假设你需要组合出 18 元,如何使硬币的数量最少 分析:我认为这个问题有点类似于 01 背包问题,很明显

算法导论笔记 多线程算法

多线程算法 相对我来说比较局限,因为 js 是单线程的,所以只做了解,后续如果要用到可以在进行进一步的掌握。 首先来讲,目前的大部分算法都是基于单线程

算法导论笔记 全点最短路径算法

复习 在我们之前的学习之中,已经了解三种不同的最短路径算法,他们在某些条件限制下拥有不同的性能 无权图 或者说权重全部相同 可以使用 广度优先搜索(借

算法导论笔记 动态规划番外篇 堆与优先队列

最近在学习动态规划的时候发现非常需要优先队列的的基础,所以转而先学习一下优先队列算法。这里就找了比较通用的堆来入手了解优先队列。 堆 首先这里的

算法导论笔记 十一 最短路径算法

最短路径 最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 假设我们拥有一条路径 P P 经过一些

算法导论笔记 十一 贪心算法 最小生成树

图论 最小生成树需要你掌握基本的图论 在书的附录中有介绍,可以先去看看 设 V 为 有向图(v,e)的顶点集 那么遍历这个图的成本为 O(V ^ 2) 如果一个有向图 G

几种排序算法

最近一直在复习排序算法,也有了不少更深入的解读,拿出来分享一下 冒泡排序 冒泡排序顾名思义,就是将一个个数字冒泡一样的推送到他该去的地方。 冒泡算

算法导论笔记 一 起步

算法 什么是算法 算法(algorithm),在数学(算学)和计算机科学之中,为任何良定义的具体计算步骤的一个序列,常用于计算、数据处理和自动推

算法导论笔记 二 分治法

名词解释 多项式级 即 n^2 n^3 可以被认为是可控的算法复杂度级别 指数级 x^n 级别 非常恐怖 分治法 分治法是一种极为重要的算法设计思想,他的核心思想就是把大问题

算法导论笔记 八 竞争性分析,自组织表

自组织表 先来理解两个概念 在线算法与离线算法 在线算法(也成为线上算法):是一个处理数据的一种方式,他不要求建立数据结构的时候所有数据源全部就绪

算法导论笔记 四 中位数与顺序统计

选择算法 所谓的选择算法,其基本规则就是从一个无序的数组中,找到第 i 小的值。 最简单的做法其实就是将数组排序,下标+1 就是它的 i。但是,就算依托

算法导论笔记 四 二叉搜索树

二叉树 二叉树本身就是非常常见的一种数据结构了,对于这种数据结构当然有一些基本操作 增删改查最大最小等等,一个二叉树的的基本操作都和二叉树的高度

算法导论笔记 四 全域哈希和完全哈希

HASH 算法的缺陷 首先,我们所了解到的所有简单的复杂的 HASH 函数总会拥有一些薄弱点,即输入一些特殊的 key 会很容易返回相同 KEY 导致多条数据插入到同一个槽中,

算法导论笔记 四 哈希表

直接寻址 相对于哈希表来说,直接寻址是一种更为简单的方法,即使用一组键集合 K 来代表一组相应的值 U,但是直接寻址受限于一个重要的缺陷,即K可能相

算法导论 七 平摊分析,表的扩增,势能方法

动态表 简单阐述一下动态表的基本思想,先建立一个表,当插入的元素大于表的大小时,建立一个新表(大小为旧表的两倍),并将旧表中的所有数据复制到新

算法导论笔记 九 动态规划

动态规划 动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过

算法导论笔记 五 扩充的数据结构、动态有序统计和区间树

这一章的主要内容其实是如何利用现有的数据结构来扩充成一个新的数据结构,并让这种新的数据结构具有一些神奇的特性。 动态顺序统计 我们在前面就学习了

算法导论笔记 六 跳跃表

跳跃表(skiplists) 跳跃表是一种增强版的链表,他能在O(lgn)的时间内完成搜索。 首先,我们熟知的链表本身具有的特性就是容易删除与增