Open Hibop opened 5 years ago
本仓库包含了多种基于 JavaScript 的算法与数据结构。
每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。
Read this in other languages: English, 繁體中文, 한국어, Polski, Français, Español, Português
数据结构是在计算机中 组织和存储数 据的一种特殊方式, 它可以高效地 访问和修改 数据。更确切地说, 数据结构是数据值的集合, 它们之间的关系、函数或操作可以应用于数据。
B - 初学者, A - 进阶
B
A
算法是如何解决一类问题的明确规范。 算法是一组精确定义操作序列的规则。
算法范式是基于类的设计的通用方法或方法的算法。 这是一个比算法概念更高的抽象, 就像一个 算法是比计算机程序更高的抽象。
BF算法 - 查找/搜索 所有可能性并选择最佳解决方案
贪心法 - 在当前选择最佳选项, 不考虑以后情况
分治法 - 将问题分成较小的部分, 然后解决这些部分
动态编程 - 使用以前找到的子解决方案构建解决方案
回溯法 - 类似于 BF算法 试图产生所有可能的解决方案, 但每次生成解决方案测试如果它满足所有条件, 那么只有继续生成后续解决方案。 否则回溯并继续寻找不同路径的解决方案。
Branch & Bound
安装依赖
npm install
执行测试
npm test
按照名称执行测试
npm test -- 'LinkedList'
Playground
你可以在./src/playground/playground.js文件中操作数据结构与算法, 并在./src/playground/__test__/playground.test.js中编写测试。
./src/playground/playground.js
./src/playground/__test__/playground.test.js
然后, 只需运行以下命令来测试你的 Playground 是否按无误:
npm test -- 'playground'
▶ YouTube
大O符号中指定的算法的增长顺序。
源: Big O Cheat Sheet.
以下是一些最常用的 大O标记法 列表以及它们与不同大小输入数据的性能比较。
JavaScript 算法与数据结构
本仓库包含了多种基于 JavaScript 的算法与数据结构。
每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。
Read this in other languages: English, 繁體中文, 한국어, Polski, Français, Español, Português
数据结构
数据结构是在计算机中 组织和存储数 据的一种特殊方式, 它可以高效地 访问和修改 数据。更确切地说, 数据结构是数据值的集合, 它们之间的关系、函数或操作可以应用于数据。
B
- 初学者,A
- 进阶B
链表B
双向链表B
队列B
栈B
哈希表B
堆B
优先队列A
字典树A
树A
二叉查找树A
AVL 树A
红黑树A
线段树 - 使用 最小/最大/总和 范围查询示例A
树状数组 (二叉索引树)A
图 (有向图与无向图)A
并查集A
布隆过滤器算法
算法是如何解决一类问题的明确规范。 算法是一组精确定义操作序列的规则。
算法主题
B
Bit 操控 - set/get/update/clear 位, 乘以/除以 二进制位, 变负 等.B
阶乘B
斐波那契数B
素数检测 (排除法)B
欧几里得算法 - 计算最大公约数 (GCD)B
最小公倍数 (LCM)B
素数筛 - 查找所有素数达到任何给定限制B
判断2次方数 - 检查数字是否为2的幂 (原生和按位算法)B
杨辉三角形A
整数拆分A
割圆术 - 基于N-gons的近似π计算B
笛卡尔积 - 多集合结果A
幂集 - 该集合的所有子集A
排列 (有/无重复)A
组合 (有/无重复)A
洗牌算法 - 随机置换有限序列A
最长公共子序列 (LCS)A
最长递增子序列A
最短公共父序列 (SCS)A
背包问题 - "0/1" and "Unbound" onesA
最大子数列问题 - BF算法 与 动态规划A
组合求和 - 查找形成特定总和的所有组合A
莱温斯坦距离 - 两个序列之间的最小编辑距离B
汉明距离 - 符号不同的位置数A
KMP算法 (克努斯-莫里斯-普拉特算法) - 子串搜索 (模式匹配)A
字符串快速查找 - 子串搜索A
最长公共子串A
正则表达式匹配B
线性搜索B
跳转搜索 (或块搜索) - 搜索排序数组B
二分查找B
插值搜索 - 搜索均匀分布的排序数组B
冒泡排序B
选择排序B
插入排序B
堆排序B
归并排序B
快速排序B
希尔排序B
计数排序B
基数排序B
深度优先搜索 (DFS)B
广度优先搜索 (BFS)B
深度优先搜索 (DFS)B
广度优先搜索 (BFS)A
戴克斯特拉算法 - 找到图中所有顶点的最短路径A
贝尔曼-福特算法 - 找到图中所有顶点的最短路径A
弗洛伊德算法 - 找到所有顶点对 之间的最短路径A
判圈算法 - 对于有向图和无向图 (基于DFS和不相交集的版本)A
普林演算法 - 寻找加权无向图的最小生成树 (MST)B
克鲁斯克尔演算法 - 寻找加权无向图的最小生成树 (MST)A
拓扑排序 - DFS 方法A
关节点 - Tarjan算法 (基于DFS)A
桥 - 基于DFS的算法A
欧拉回径与一笔画问题 - Fleury的算法 - 一次访问每个边A
哈密顿图 - 恰好访问每个顶点一次A
强连通分量 - Kosaraju算法A
旅行推销员问题 - 尽可能以最短的路线访问每个城市并返回原始城市B
汉诺塔B
旋转矩阵 - 原地算法B
跳跃 游戏 - 回溯, 动态编程 (自上而下+自下而上) 和贪婪的例子B
独特(唯一) 路径 - 回溯, 动态编程和基于Pascal三角形的例子B
雨水收集 - 诱捕雨水问题 (动态编程和暴力版本)A
八皇后问题A
骑士巡逻算法范式
算法范式是基于类的设计的通用方法或方法的算法。 这是一个比算法概念更高的抽象, 就像一个 算法是比计算机程序更高的抽象。
BF算法 - 查找/搜索 所有可能性并选择最佳解决方案
B
线性搜索B
雨水收集 - 诱导雨水问题A
最大子数列A
旅行推销员问题 - 尽可能以最短的路线访问每个城市并返回原始城市贪心法 - 在当前选择最佳选项, 不考虑以后情况
B
跳跃游戏A
背包问题A
戴克斯特拉算法 - 找到所有图顶点的最短路径A
普里姆算法 - 寻找加权无向图的最小生成树 (MST)A
克鲁斯卡尔算法 - 寻找加权无向图的最小生成树 (MST)分治法 - 将问题分成较小的部分, 然后解决这些部分
B
二分查找B
汉诺塔B
杨辉三角形B
欧几里得算法 - 计算最大公约数 (GCD)B
跳跃游戏B
归并排序B
快速排序B
树深度优先搜索 (DFS)B
图深度优先搜索 (DFS)A
排列 (有/无重复)A
组合 (有/无重复)动态编程 - 使用以前找到的子解决方案构建解决方案
B
斐波那契数B
跳跃游戏B
独特路径B
雨水收集 - 疏导雨水问题A
莱温斯坦距离 - 两个序列之间的最小编辑距离A
最长公共子序列 (LCS)A
最长公共子串A
最长递增子序列A
最短公共子序列A
0-1背包问题A
整数拆分A
最大子数列A
弗洛伊德算法 - 找到所有顶点对之间的最短路径A
贝尔曼-福特算法 - 找到所有图顶点的最短路径回溯法 - 类似于 BF算法 试图产生所有可能的解决方案, 但每次生成解决方案测试如果它满足所有条件, 那么只有继续生成后续解决方案。 否则回溯并继续寻找不同路径的解决方案。
B
跳跃游戏B
独特路径A
哈密顿图 - 恰好访问每个顶点一次A
八皇后问题A
骑士巡逻A
组合求和 - 从规定的总和中找出所有的组合Branch & Bound
如何使用本仓库
安装依赖
执行测试
按照名称执行测试
Playground
你可以在
./src/playground/playground.js
文件中操作数据结构与算法, 并在./src/playground/__test__/playground.test.js
中编写测试。然后, 只需运行以下命令来测试你的 Playground 是否按无误:
有用的信息
引用
▶ YouTube
大O符号
大O符号中指定的算法的增长顺序。
源: Big O Cheat Sheet.
以下是一些最常用的 大O标记法 列表以及它们与不同大小输入数据的性能比较。
数据结构操作的复杂性
数组排序算法的复杂性