README

状态： 已弃用

Hack Fast Algos 将所有最流行的速度和空间效率高的算法汇集到一个库中。这些文件完全用 Hack 编写，因此它们将与启用 Hack 的 HHVM 安装一起工作。

内容

目的
算法列表
数据结构列表
面试题/谜题列表
关于较慢算法的说明
为什么 X 算法没有出现？
贡献
获取该库的另一种语言版本
致谢和进一步学习

目的

此库的主要目的是帮助网络开发者学习算法和数据结构。如果您打算将库作为学习或教学工具使用，请注意，通常有多种方式可以编写算法概念。例如，MergeSort 不需要异步运行其递归，某些编程语言不支持异步工作流程。任何优秀算法设计者的座右铭是，“我们能使其更好（更快/更内存效率/更注重内存）吗？”

公司依靠速度和空间效率高的代码来确保其网站和项目顺利运行。您会发现其中一些算法仅在大型数据集（例如，大量数组元素）上效率高，或者需要针对当前任务适当的参数（例如，Quick Sort 参数的配置）。我已经使用渐近符号注释了每个算法的运行时间和存储需求。

请注意，HHVM 主要用 C++ 和 C 编写，并具有大量内置功能，这些功能使用这些算法。（例如，sort() 使用 Quick Sort 的实现）因此，通常使用内置功能更快。然而，内置函数并不总是提供处理大型数据集时所需的精细调整能力。

算法列表

每个算法都归入一个类似算法的类别。以下是类别列表，之后是该类中定义的算法列表。

算法
BFS
BucketSort
- Bucket Soft 排序算法
ConvexHull
- 使用 Graham Scan 计算凸包。
CountingSort
- 计数排序算法
Cryptography
- 生成安全随机数的算法
DFS
- 基于 DFS 的各种算法实现
DijkstrasAlgorithm
- 使用最小优先队列实现 Dijkstra 算法
FordFulkerson
- 基于 Min-Cut 的最大流算法
几何
Graph
GraphFormat
- 在边列表、邻接列表和邻接矩阵之间进行转换。
HuffmanCode
- Huffman 编码
- Huffman 解码
Kosaraju
- Kosaraju 的强连通分量算法实现
KSum
- 2-Sum 和 3-Sum 求解器实现
LZW
数学
MatrixMultiply
- Strassen 矩阵乘法
MatrixRotate
- 旋转和翻转矩阵的算法
MedianHeap
- 在整数流中获取中位数。
MergeSort
- Merge Sort 排序算法
MostFrequentWord
- 计算给定文本中最频繁的单词。
MST
- 最小生成树算法
MurmurHash3
- MurmurHash3 的实现
Palindrome
- isPalindrome
- Manacher算法用于在所需文本中查找最长回文子串
分区
- 围绕一个整数对向量进行分区。
波兰前缀表示法
- 波兰前缀表示法的实现
QuickSelect
- 此QuickSelect实现用于在向量中选择第k小的元素。
QuickSort
- 快速排序算法
RabinKarp
- Rabin-Karp子串搜索算法的实现
- Rabin指纹散列的实现
RadixSort
- 用于LSD和MSD的实现
RegEx
- 正则表达式解释器的初步实现
- Grep
RunLengthCompression
- 二进制数据的行程压缩算法
Search
- 二分搜索
- 暴力搜索
ShortestPath
- 最短路径问题的算法
Sort
- 选择排序
- 冒泡排序
- 插入排序
- 希尔排序（使用Tokunda的间隔算法）
- HeapSort
- Fisher-Yates Shuffle
Strings
- 后缀数组
- 最长前缀
- 最长重复子串
SubString
- 两种暴力方法，它们执行相同的功能，但编写方式不同
- KMP [Knuth-Morris-Pratt]
- KMP改进版
- Boyer-Moore
TopSort
- 拓扑排序的实现

数据结构列表

所有数据结构都使用命名空间\HackFastAlgos\DataStructure。以下是数据结构列表。使用比较函数（compare()）的数据结构可能重写了该方法，以扩展该数据结构的功能。因此，所有数据都使用泛型类型T，在适当的情况下。

AdjList
- 图的邻接表
AdjMatrix
- 图的邻接矩阵对象
AVLTree
- AVL树实现
Bag
- 包实现
BloomFilter
- Bloom过滤器实现
BPlusTree
BST
- BST是二叉搜索树的一种实现。
DoublyLinkedList
- 双链表实现
EdgeList
- 图的边列表对象
GameTree
GraphNode
- 用于图算法的节点
HashTableChain
- 使用双链表实现的散列表
HashTableOA
- 使用开放寻址策略实现的散列表
Heap
- 支持最小堆和最大堆类型的二叉堆实现
Indexer
- 在文件中查找单词，并获取该单词在所有出现的文件中的上下文
IntervalTree
KDTree
LinkedListNode
- 用于链表的节点
LRUCache
- 实现一个最不常用缓存，当缓存满时删除最不常用的项目并添加新项目。
OrderStatisticTree
- 基于AVLTree的有序统计树实现，具有select()和getRank()功能。
PriorityQueue
- 优先队列实现
Queue
- 实现一个普通的队列
RBTree
- RBTree是实现左倾红黑树的一种实现。
RWayTrie
- 使用整数值实现的R-Way-Trie
Schedule
- 任务调度器的实现
Set
- 集合实现
SplayTree
Stack
- 堆栈实现
StringBuffer
- 一次性将所有字符串连接起来，而不是使用Theta(n)运行时间来连接字符串（如使用 .= 或类似方法）。
TernarySearchTrie
- 三元搜索树（TST）的实现
TwoThreeTree
TreeNode
- 用于树和Trie的节点
TrieNode
- 在R-Way Trie中使用的节点
UnionFind
- 并查集数据结构也称为不相交集或合并查找。

面试难题列表

所有面试问题谜题使用命名空间 \HackFastAlgos\Interview。以下是该库中包含的流行面试问题列表。

CompressString

谜题：实现一个算法，使用每个字符的计数进行基本的字符串压缩。如果压缩后的字符串比原始字符串长，则返回原始字符串。
DialPad

谜题：返回电话号码的所有可能的字母组合。
FizzBuzz

谜题：编写一个算法，遍历0到100的数字，对于所有3的倍数输出"Fizz"。对于所有5的倍数输出"Buzz"。如果一个数字是5和3的公倍数，则输出"FizzBuzz"。例如：0:FizzBuzz 3:Fizz 5:Buzz ...)
Laundry

通过Gainlo参加的我的亚马逊实践面试

谜题：有N台洗衣机器。它们具有无限容量。现在一车衣物被卸载用于洗涤，并随机分配给每台机器。在这个过程中，经理没有平衡衣物的清洗负荷。现在需要重新平衡。

重新平衡是通过轮次进行的。每次，一台机器最多可以将一件衣物转移到其相邻的机器。机器i的相邻机器是机器i-1和i+1（机器1和N只有一个相邻机器，分别是2和N-1）。

重新平衡的目标是使所有机器的衣物数量相同。给定初始分配给每台机器的衣物数量，您需要确定达到每个机器都有相同数量衣物的最小轮次，或者确定这样的重新平衡是不可能的。
Permutations

谜题1：找出给定字符串的所有排列。

谜题2：检查一个字符串是否是另一个字符串的排列。
RansomMagazine

谜题：编写一个算法，查看赎金信中的所有单词是否都包含在杂志中。
ReplaceChar

谜题：在给定的字符串中将空格替换为%20。
ResetVector

谜题：一个连续整数的向量被旋转，使得数字在向量中的某个位置重新计数。找到数字开始计数的键。（例如，在Vector{6,7,8,9,0,1,2,3,4,5}中，重置点是4，因为0是最低的数字。）
StringReverse

谜题：实现一个算法来反转一个字符串。
StringRotation

谜题：编写代码来检查一个字符串是否是第二个字符串的旋转。
TreeLis
通过Gainlo参加的我的亚马逊实践面试

谜题：给定一棵二叉树，找到最大独立集的大小。这意味着最终集中的两个节点没有直接的父子关系。
```
         a1
        /  \
       a2   a3
      / \    \
     a4  a5  a6
         / \
        a7  a8

        Answer: a1,a4,a7,a8,a6 ---> LIS is 5
```
UniqueChars

谜题：检查一个字符串是否有所有唯一的字符，不使用额外的数据结构。
ZeroMatrix

谜题：编写一个算法来检查MxN矩阵是否存在值为零的元素。每次发现零元素时，将该元素的行和列都设为零。

关于较慢算法的说明

该库中包含了一些“较慢”的算法，让我解释一下为什么我选择包含它们。首先，我将定义我在讨论算法速度时所指的含义。

当测量算法的速度时，计算机科学家会谈论渐近表示法。有三种类型的渐近表示法：大O、大Ω和大Θ。

大O是最受欢迎的，因为它表示运行时间的上界，意味着在最坏的情况下，算法的运行时间不会慢于大O时间。大Ω表示大O的反面。它表示即使在最佳情况下，算法的运行时间也不会快于大Ω。最后，我们有大Θ，它表示无论你向算法中塞入什么数据，算法都将始终以大Θ时间运行。

在计算渐近表示法时，你会丢弃低阶项（系数和常数），因为它们对运行时间的影响不大。因此，渐近表示法在定义大数据集的运行时间时更为准确，而在定义较小的数据集时则不太准确。因此，如果你使用SelectionSort对一个包含四个元素的向量进行排序，你可能会发现它比使用MergeSort或QuickSort更快。

我包含“较慢”算法的另一个原因是它们仍然是一种比较不同算法的方式。

为什么Y算法的X应用没有包含在库中？

Y算法的X应用没有包含在库中的原因很简单，那就是你还没有编写它！每个算法都可以适应多种应用，而且有无限种可能的应用。简单来说，我无法编写每个可能的算法的实现或实现该算法的每个可能的应用。我选择了每个算法最受欢迎的应用，如果你认为库中缺少了某个流行算法，请将其编写出来，然后创建一个pull request。

贡献

在创建pull request时，请检查以下内容。

遵守敏捷标准。
遵循你面前看到的编码标准。本项目使用PSR-1和PSR-2编码标准。
在你的文档块中，记得标明算法的渐近表示法。使用最严格的表示法。
始终用Hack编写你的代码！Hack比PHP更快，并且可以减少你的代码可能导致的错误数量。为了确保代码质量，你必须使用类型检查。
如果你正在创建新的对象，请使用“HackFastAlgos”命名空间，以防止与其他项目发生代码冲突。
每个文件的名字与其包含的类相同，并且每个文件只能有一个类。例外情况是，你可以在主类之前包含异常类。
为每种类型的异常始终抛出自定义异常。以下是你命名异常的格式。 <CLASS><TYPE>Exception（例如：DoublyLinkedListInvalidIndexException）

本库在其他语言中的情况

目前还没有人在其他语言中创建HackFastAlgos的端口。如果你创建了该包的自己的端口，请让我知道，这样我就可以在本文档的这部分列出它。

致谢和进一步学习资源

本库中的许多算法在计算机科学社区中都是众所周知的算法。各种科学家发明了我实现的算法。在适用的情况下，我已经链接到维基百科或其他感兴趣的位置来描述算法和数据结构。你可以通过访问这些页面来了解算法的发明者。

以下是我第一次学习本库中的算法和数据结构的来源列表。以下大部分资源都是MOOCs的免费资源。如果你对算法和数据结构感兴趣，请参加以下课程，阅读书籍或网站。虽然这个库是理解材料的极好方式，但它并没有涵盖以下资源中的所有内容。

为了完全理解内容，请手动编写这个库的副本进行练习。如果你用除Hack以外的语言编写它，请参阅上面的“本库在其他语言中的情况”部分。

关于Coursera荣誉守则的注意事项

Coursera荣誉守则禁止学生在Coursera作业中发布答案。具体来说，它作出了以下声明。

我不会将作业、测验、考试、项目以及其他作业（以下简称“作业”）的解决方案提供给任何人（除非作业明确允许共享解决方案）。这包括我写的解决方案，以及课程工作人员或其他人员提供的任何解决方案。

因此，这个图书馆尊重荣誉守则，不包括此类材料。我特别没有为我在这个图书馆使用的课程完成Coursera作业，以便这个图书馆与任何作业都保持独立。如果这个图书馆中包含的任何材料看起来像是作业的答案，那纯属巧合，并非有意为之。

cozylife / hackfastalgos

维护者

详细信息