javascript-algorithms - 📝用 JavaScript 实现的算法和数据结构，附有详情链接

Created at: 2018-03-24 15:47:04

Language: JavaScript

编号: https://github.com/trekhleb/javascript-algorithms

License: MIT

JavaScript 算法和数据结构

🇺🇦乌克兰正在受到俄罗斯军队的袭击。平民正在被杀害。居民区正在遭到轰炸。

通过乌克兰国家银行帮助乌克兰

通过储蓄生命基金帮助乌克兰

有关乌克兰 war.ukraine.ua 和外交部的更多信息

该存储库包含许多流行算法和数据结构的基于 JavaScript 的示例。

每种算法和数据结构都有自己单独的自述文件，其中包含相关的解释和进一步阅读的链接（包括YouTube视频的链接）。

用其他语言阅读： 简体中文， 繁體中文， 한국어， 日本語，波兰语，法语， 西班牙语， 葡萄牙语， Русский， Türkçe， 意大利语， 印度尼西亚语， Українська， 阿拉伯语，越南，德语

☝ 请注意，此项目仅用于学习和研究目的，不用于生产。

数据结构

数据结构是在计算机中组织和存储数据的一种特殊方式，以便可以有效地访问和修改数据。更准确地说，数据结构是数据值、它们之间的关系以及可应用于数据的函数或操作的集合。

- 初级， - 高级

```
B
```
链表
```
B
```
双向链表
```
B
```
队列
```
B
```
叠
```
B
```
哈希表
```
B
```
堆 - 最大和最小堆版本
```
B
```
优先级队列
```
A
```
特里
```
A
```
树
- ```
A
```
  二叉搜索树
- ```
A
```
  AVL 树
- ```
A
```
  红黑树
- ```
A
```
  段树 - 包含最小/最大/总和范围查询示例
- ```
A
```
  芬威克树（二叉索引树）
```
A
```
图形（有向和无向）
```
A
```
不相交集 - 联合-查找数据结构或合并-查找集合
```
A
```
布隆过滤器
```
A
```
LRU 缓存 - 最近最少使用的（LRU）缓存

算法

算法是如何解决一类问题的明确规范。它是一组精确定义操作序列的规则。

- 初级， - 高级

按主题分类的算法

数学
- ```
B
```
  位操作 - 设置/获取/更新/清除位，乘法/除以二，使负数等。
- ```
B
```
  二进制浮点数 - 浮点数的二进制表示形式。
- ```
B
```
  阶乘
- ```
B
```
  斐波那契数 - 经典和封闭形式版本
- ```
B
```
  素因数 - 找到素因数并使用哈代-拉马努金定理对其进行计数
- ```
B
```
  素数检验（试验除法）
- ```
B
```
  欧几里得算法 - 计算最大公约数（GCD）
- ```
B
```
  最小公倍数（LCM）
- ```
B
```
  埃拉托色尼筛 - 找到任何给定极限的所有素数
- ```
B
```
  是 2 的幂 - 检查数字是否是 2 的幂（朴素和按位算法）
- ```
B
```
  帕斯卡三角形
- ```
B
```
  复数 - 复数及其基本运算
- ```
B
```
  弧度和度 - 弧度到度和向后转换
- ```
B
```
  快速供电
- ```
B
```
  霍纳方法 - 多项式求值
- ```
B
```
  矩阵 - 矩阵和基本矩阵运算（乘法、换位等）
- ```
B
```
  欧几里得距离 - 两点/向量/矩阵之间的距离
- ```
A
```
  整数分区
- ```
A
```
  平方根 - 牛顿法
- ```
A
```
  刘辉π算法 - 基于N-gons的近似π计算
- ```
A
```
  离散傅里叶变换 - 将时间函数（信号）分解为构成它的频率
集
- ```
B
```
  笛卡尔积 - 多套积
- ```
B
```
  费舍尔-耶茨洗牌 - 有限序列的随机排列
- ```
A
```
  幂集 - 一个集的所有子集（按位、回溯和级联解决方案）
- ```
A
```
  排列（有重复和不重复）
- ```
A
```
  组合（有和没有重复）
- ```
A
```
  最长公共子序列（LCS）
- ```
A
```
  最长递增子序列
- ```
A
```
  最短公共超序列（SCS）
- ```
A
```
  背包问题 - “0/1”和“未绑定”问题
- ```
A
```
  最大子阵列 - “蛮力”和“动态编程”（Kadane 的）版本
- ```
A
```
  组合总和 - 查找形成特定总和的所有组合
字符串
- ```
B
```
  汉明距离 - 符号不同的位置数
- ```
B
```
  回文 - 反向检查字符串是否相同
- ```
A
```
  Levenshtein 距离 - 两个序列之间的最小编辑距离
- ```
A
```
  高德纳-莫里斯-普拉特算法（KMP算法） - 子字符串搜索（模式匹配）
- ```
A
```
  Z 算法 - 子字符串搜索（模式匹配）
- ```
A
```
  拉宾卡普算法 - 子字符串搜索
- ```
A
```
  最长的公共子字符串
- ```
A
```
  正则表达式匹配
搜索
- ```
B
```
  线性搜索
- ```
B
```
  跳转搜索（或块搜索） - 在排序数组中搜索
- ```
B
```
  二叉搜索 - 在排序数组中搜索
- ```
B
```
  插值搜索 - 在均匀分布的排序数组中搜索
排序
- ```
B
```
  气泡排序
- ```
B
```
  选择排序
- ```
B
```
  插入排序
- ```
B
```
  堆排序
- ```
B
```
  合并排序
- ```
B
```
  快速排序 - 就地和非就地实现
- ```
B
```
  贝壳排序
- ```
B
```
  计数排序
- ```
B
```
  基数排序
- ```
B
```
  存储桶排序
链表
- ```
B
```
  直线遍历
- ```
B
```
  反向遍历
树
- ```
B
```
  深度优先搜索（DFS）
- ```
B
```
  广度优先搜索（BFS）
图
- ```
B
```
  深度优先搜索（DFS）
- ```
B
```
  广度优先搜索（BFS）
- ```
B
```
  克鲁斯卡尔算法 - 查找加权无向图的最小生成树（MST）
- ```
A
```
  Dijkstra 算法 - 从单个顶点找到到所有图形顶点的最短路径
- ```
A
```
  贝尔曼-福特算法 - 从单个顶点找到到所有图形顶点的最短路径
- ```
A
```
  弗洛伊德-沃歇尔算法 - 找到所有顶点对之间的最短路径
- ```
A
```
  检测周期 - 适用于有向图和无向图（基于 DFS 和不相交集的版本）
- ```
A
```
  Prim 算法 - 查找加权无向图的最小生成树（MST）
- ```
A
```
  拓扑排序 - DFS 方法
- ```
A
```
  关节点 - Tarjan算法（基于DFS）
- ```
A
```
  网桥 - 基于 DFS 的算法
- ```
A
```
  欧拉路径和欧拉回路 - 弗勒里算法 - 精确访问每条边一次
- ```
A
```
  哈密顿循环 - 精确访问每个顶点一次
- ```
A
```
  强连接组件 - Kosaraju 算法
- ```
A
```
  旅行推销员问题 - 访问每个城市并返回始发城市的最短路线
密码学
- ```
B
```
  多项式哈希 - 基于多项式的滚动哈希函数
- ```
B
```
  铁路围栏密码 - 用于编码消息的换位密码算法
- ```
B
```
  凯撒密码 - 简单的替换密码
- ```
B
```
  希尔密码 - 基于线性代数的替换密码
机器学习
- ```
B
```
  NanoNeuron - 7个简单的JS函数，说明机器如何实际学习（向前/向后传播）
- ```
B
```
  k-NN - k-最近邻分类算法
- ```
B
```
  k 均值 - k 均值聚类算法
图像处理
- ```
B
```
  接缝雕刻 - 内容感知图像大小调整算法
统计学
- ```
B
```
  加权随机 - 根据项目的权重从列表中选择随机项目
进化算法
- ```
A
```
  遗传算法 - 如何应用遗传算法训练自动泊车的示例
未分类
- ```
B
```
  河内塔
- ```
B
```
  方阵旋转 - 就地算法
- ```
B
```
  跳跃游戏 - 回溯，动态编程（自上而下+自下而上）和贪婪的例子
- ```
B
```
  独特路径 - 回溯、动态规划和基于 Pascal's 三角形的示例
- ```
B
```
  雨水梯田 - 捕获雨水问题（动态编程和暴力破解版本）
- ```
B
```
  递归楼梯 - 计算到达顶部的方法数量（4 种解决方案）
- ```
B
```
  买入卖出股票的最佳时机 - 分而治之和一次通过的例子
- ```
A
```
  N-皇后问题
- ```
A
```
  骑士之旅

范式算法

算法范式是一种通用方法或方法，它是一类算法设计的基础。它是高于算法概念的抽象，就像算法是高于计算机程序的抽象一样。

蛮力 - 查看所有可能性并选择最佳解决方案
- ```
B
```
  线性搜索
- ```
B
```
  雨水梯田 - 捕获雨水问题
- ```
B
```
  递归楼梯 - 计算到达顶部的方式数量
- ```
A
```
  最大子阵列
- ```
A
```
  旅行推销员问题 - 访问每个城市并返回始发城市的最短路线
- ```
A
```
  离散傅里叶变换 - 将时间函数（信号）分解为构成它的频率
贪婪 - 选择当前时间的最佳选项，而不考虑未来
- ```
B
```
  跳跃游戏
- ```
A
```
  未绑定背包问题
- ```
A
```
  Dijkstra 算法 - 找到所有图形顶点的最短路径
- ```
A
```
  Prim 算法 - 查找加权无向图的最小生成树（MST）
- ```
A
```
  克鲁斯卡尔算法 - 查找加权无向图的最小生成树（MST）
分而治之 - 将问题分成更小的部分，然后解决这些部分
- ```
B
```
  二叉搜索
- ```
B
```
  河内塔
- ```
B
```
  帕斯卡三角形
- ```
B
```
  欧几里得算法 - 计算最大公约数（GCD）
- ```
B
```
  合并排序
- ```
B
```
  快速排序
- ```
B
```
  树深度优先搜索（DFS）
- ```
B
```
  图形深度优先搜索（DFS）
- ```
B
```
  矩阵 - 生成和遍历不同形状的矩阵
- ```
B
```
  跳跃游戏
- ```
B
```
  快速供电
- ```
B
```
  买入卖出股票的最佳时机 - 分而治之和一次通过的例子
- ```
A
```
  排列（有重复和不重复）
- ```
A
```
  组合（有和没有重复）
- ```
A
```
  最大子阵列
动态规划 - 使用以前找到的子解决方案构建解决方案
- ```
B
```
  斐波那契数
- ```
B
```
  跳跃游戏
- ```
B
```
  独特路径
- ```
B
```
  雨水梯田 - 捕获雨水问题
- ```
B
```
  递归楼梯 - 计算到达顶部的方式数量
- ```
B
```
  接缝雕刻 - 内容感知图像大小调整算法
- ```
A
```
  Levenshtein 距离 - 两个序列之间的最小编辑距离
- ```
A
```
  最长公共子序列（LCS）
- ```
A
```
  最长的公共子字符串
- ```
A
```
  最长递增子序列
- ```
A
```
  最短的共超序列
- ```
A
```
  0/1 背包问题
- ```
A
```
  整数分区
- ```
A
```
  最大子阵列
- ```
A
```
  贝尔曼-福特算法 - 找到所有图形顶点的最短路径
- ```
A
```
  弗洛伊德-沃歇尔算法 - 找到所有顶点对之间的最短路径
- ```
A
```
  正则表达式匹配
回溯 - 与蛮力类似，尝试生成所有可能的解决方案，但每次生成下一个解决方案时，你都会测试它是否满足所有条件，然后才继续生成后续解决方案。否则，回溯，走上寻找解决方案的不同道路。通常，使用状态空间的 DFS 遍历。
- ```
B
```
  跳跃游戏
- ```
B
```
  独特路径
- ```
B
```
  幂集 - 一个集的所有子集
- ```
A
```
  哈密顿循环 - 精确访问每个顶点一次
- ```
A
```
  N-皇后问题
- ```
A
```
  骑士之旅
- ```
A
```
  组合总和 - 查找形成特定总和的所有组合
Branch & Bound - 记住在回溯搜索的每个阶段找到的最低成本解决方案，并使用迄今为止找到的最低成本解决方案的成本作为问题最低成本解决方案成本的下限，以便丢弃成本大于迄今为止找到的最低成本解决方案的部分解决方案。通常，BFS 遍历与状态空间树的 DFS 遍历结合使用。

如何使用此存储库

安装所有依赖项

npm install

运行 ESLint

你可能需要运行它来检查代码质量。

npm run lint

运行所有测试

npm test

按名称运行测试

npm test -- 'LinkedList'

故障排除

如果 linting 或测试失败，请尝试删除该文件夹并重新安装 npm 包：

node_modules

rm -rf ./node_modules
npm i

还要确保你使用的是正确的节点版本（）。如果你使用 nvm 进行节点版本管理，则可以从项目的根文件夹运行，并且将选取正确的版本。

>=16

nvm use

操场

你可以在文件中使用数据结构和算法，并在中为其编写测试。

./src/playground/playground.js

./src/playground/__test__/playground.test.js

然后只需运行以下命令即可测试你的操场代码是否按预期工作：

npm test -- 'playground'

有用信息

引用

大O表示法

大 O 表示法用于根据算法的运行时间或空间需求如何随着输入大小的增长而增长对算法进行分类。在下面的图表中，你可能会找到以 Big O 表示法指定的算法最常见的增长顺序。

资料来源：大O备忘单。

以下是一些最常用的 Big O 符号列表，以及它们与不同大小的输入数据的性能比较。

大O表示法	类型	10 个元素的计算	100 个元素的计算	1000 个元素的计算
O（1）	不断	1	1	1
O（对数 N）	对数的	3	6	9
O（N）	线性	10	100	1000
O（N log N）	n 日志（n）	30	600	9000
O（N^2）	二次	100	10000	1000000
O（2^N）	指数	1024	1.26e+29	1.07e+301
O（N！	阶乘	3628800	9.3e+157	4.02e+2567

数据结构操作复杂性

数据结构	访问	搜索	插入	删除	评论
数组	1	n	n	n
叠	n	n	1	1
队列	n	n	1	1
链表	n	n	1	n
哈希表	-	n	n	n	在完美哈希函数的情况下，成本将是 O（1）
二叉搜索树	n	n	n	n	在平衡的情况下，树木成本将是O（log（n））
B树	日志（n）	日志（n）	日志（n）	日志（n）
红黑树	日志（n）	日志（n）	日志（n）	日志（n）
AVL 树	日志（n）	日志（n）	日志（n）	日志（n）
布隆过滤器	-	1	1	-	搜索时可能会出现误报

数组排序算法复杂性

名字	最好	平均	糟糕	记忆	稳定	评论
气泡排序	n	n²	n²	1	是的
插入排序	n	n²	n²	1	是的
选择排序	n²	n²	n²	1	不
堆排序	n 日志（n）	n 日志（n）	n 日志（n）	1	不
合并排序	n 日志（n）	n 日志（n）	n 日志（n）	n	是的
快速排序	n 日志（n）	n 日志（n）	n²	日志（n）	不	快速排序通常使用 O（log（n））堆栈空间就地完成
外壳排序	n 日志（n）	取决于间隙顺序	n （log（n）^）2	1	不
计数排序	n + r	n + r	n + r	n + r	是的	r - 数组中的最大数字
基数排序	n * k	n * k	n * k	n + k	是的	k - 最长键的长度

项目支持者

你可以通过 ️ GitHub 或 ❤️️ Patreon 支持❤️此项目。

支持这个项目的人

∑ = 1

作者

@trekhleb

更多关于 JavaScript 和算法的项目和文章 trekhleb.dev