algorithms

发表于 | 分类于
字数统计: 5.2k

摊还分析法

栈

常见题目：实现浏览器前进后退功能，表达式求解，括号匹配

队列

队列可用在池化技术中，用于请求的排队等待

循环队列

实现的要点是确定好队满和队空的判定条件

阻塞队列

生产者-消费者模型

并发队列

基于CAS实现无锁并发队列

递归

满足以下三个条件的问题可以使用递归：

  1. 一个问题可以分解为多个子问题

  2. 该问题与子问题的数据规模不一样，但解决思路一样

  3. 存在递归终止条件

我们找出问题与子问题的关系，写出递推公式，找出终止条件，根据这两项就可以直接得出代码。

我们思考递归时，不用去想每一层的调用关系和每一个步骤，因为这样的思考人脑很难去抽象。我们需要去假定子问题已经被解决，在子问题被解决的基础上去思考新问题。

递归是借助栈来实现的，所以用递归实现的地方都能改为迭代循环的方式来实现。

常见题目：斐波那契数列、跳蛙跳台阶、二叉树遍历

位运算

a&(a-1)：相当于将a最右边的1变成0

常见题目：统计二进制中1的个数、判断是否2的幂次、m变成n需要变动几个二进制

数组

当我们对数组内的元素进行删除时，可以不去删除和搬移元素，可以先标记该元素已被删除，等到数组没有更多空间时再一起处理。

这个思想与JVM标记清除的GC算法一样。

链表

写完链表代码后，需要检查边界条件是否正确：

  1. 链表为空
  2. 链表只有1个节点
  3. 链表只有2个节点
  4. 代码处理头尾节点是否正确

单链表

单链表的操作比较简单，遍历只能单向从头到尾。

快慢指针常作为单链表解决问题的辅助手段。

常见题目：链表反转，环的检测，求入环点，有序链表合并，求倒数第k个节点，回文单链表，求链表中间节点

循环链表

常见问题：约瑟夫问题

双向链表

工程中双向链表较为常用，因为它能在O(1)时间找到前驱节点。

例如Java中的LinkedList、LinkedHashMap中都涉及到双向链表。

常见题目：LRU缓存（LinkedHashMap与LRU缓存原理是一样的，实现上有个小技巧：双端链表加一个header，双端链表其实是一个循环链表，这么做就不用判断表头表尾，相当于哨兵）

排序

可以利用稳定排序算法对多个字段排序。比如对订单按照时间先后排序，相同时间的订单按照金额大小再排序。可以先按照金额进行排序，再按照时间进行稳定排序。

O(n^2)

  • 插入排序。工程上针对小规模数据较常用，相比冒泡排序，插入有着较少的交换次数；相比选择排序，插入是稳定的。
  • 冒泡排序。比较并交换相邻两个元素。
  • 选择排序。

O(n*logn)

归并排序

优点是不管什么情况下，时间复杂度都稳定在O(n*logn)。缺点是空间复杂度为O(n)，需要辅助空间，工程中较少使用。

*常见题目： 现在有10个接口访问日志文件，每个日志文件大小约300MB，每个文件里的日志都是按照时间戳从小到大排序的。希望将这10个较小的日志文件，合并为1个日志文件，合并之后的日志仍然按照时间戳从小到大排列。机器内存只有1GB。

快速排序

工程上较为常用。分区点的选择是关键，如果每次都能选择到中间节点，时间复杂度是O(n*logn)。如果每次分区点都是头尾节点，那么时间复杂度就会退化为O(n^2)。工程中可以使用三数取中法或者随机法选择分区点。

常见题目：求第K大的数

堆排序

O(n)

排序能做到线性时间是因为这些排序不是基于比较的。

桶排序

桶排序对排序数据的要求非常严格，要求数据能平均地分配到各个桶中。

桶排序比较适合用在外部排序中。

常见题目： 有10GB的订单数据，希望按订单金额进行排序，但是内存有限，只有几百MB，没办法一次性把10GB的数据都加载到内存中。

根据年龄给100万用户排序。

计数排序

计数排序属于桶排序，这里把它单独拎出来是因为它是特殊的桶排序。

相比于桶排序，计数排序中桶的粒度更小，小到只有一个单位，就省去了桶内排序。

计数排序适用于数据范围不大的情况。

基数排序

基数排序要求数据可以分割出“位”来比较，且“位”的数据范围不能太大。对每一“位”使用桶排序，从低位一直排序到高位。

常见题目：对10万个手机号码从小到大排序

二分查找

二分查找对数据有以下要求：

  1. 数据需要是有序的
  2. 数据存储在数组中
  3. 数据集太小（顺序遍历即可）或太大（数组占用连续空间）都不合适二分查找

二分查找时间复杂度是O(logn)，对数级有时比常数级还要高效，因为常数级中的常数可能会很大。

能用二分查找解决的问题，一般也能用动态数据结构散列表和二叉树解决，他们有一个区别是：二分查找由于依赖数组，因此它的占用内存会小一点，不需要存储指针等额外数据。

如果用链表来实现二分查找，时间复杂度会是O(n)。

二分查找适合查找近似的数值，它有4种变体问题：

  1. 查找第一个值等于给定值的元素
  2. 查找最后一个值等于给定值的元素
  3. 查找第一个大于等于给定值的元素
  4. 查找最后一个小于等于给定值的元素

常见题目： 有12万条IP区间与归属地的对应关系，如何快速定位出一个IP地址的归属地。

1
2
[202.102.133.0, 202.102.133.255]  山东东营市 
[202.102.135.0, 202.102.136.255]  山东烟台

循环数据的二分查找

跳表

跳表可以理解为链表版的“二分”查找。时间复杂度为O(logn)，空间复杂度为O(n)。跳表出现得比红黑树晚，在类库中有现成的红黑树代码，但没有跳表。

常见题目：为什么redis使用跳表而不是红黑树。（1.跳表实现比较简单；2.在区间查找上，跳表效率比红黑树高）

散列表

散列表来源于数组，它借助散列函数对数组这种数据结构进行扩展。散列表有三个核心问题：散列函数设计、散列冲突解决、扩容策略。

冲突解决方法：开放寻址法和链表法。

当数据量比较小、装载因子小的时候，适合采用开放寻址法。

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表

ThreadLocalMap通过线性探测的开放寻址解决冲突。

常见题目：

  1. Word单词拼写检查
  2. 假设有10万条URL访问日志，如何按照访问次数给URL排序
  3. 有两个字符串数组，每个数组大约有10万条字符串，如何快速找出两个数组中相同的字符串
  4. LRU缓存
  5. 配合跳表组成Redis有序集合

哈希算法

哈希算法有以下特点：

  • 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
  • 对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同；
  • 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
  • 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

常用的哈希算法有MD5、SHA、DES、AES等。根据鸽巢原理，哈希算法一定是会有冲突的。

哈希算法有以下几点应用：

  1. 安全加密

  2. 唯一标识

  3. 数据校验

  4. 散列函数

  5. 负载均衡。同一客户端请求路由到同一机器。

  6. 数据分片。

    统计1T的搜索词日志，计算每个搜索词被搜索次数。

    判断某张图片是否在图库中，图库有1亿张图片。

  7. 分布式存储。

    对数据提取哈希，决定存储在哪台机器上。若新增机器，所有的数据都需要重新计算哈希。为了解决这个问题，可以使用一致性哈希算法，该算法不需要搬移全部数据，只需要将某几个小区间的数据搬移到新机器中。

二叉树

满二叉树

除叶子节点外，每个节点都有左右两个子节点。

完全二叉树

有一种二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

完全二叉树比较适合用数组来存储，由于不需要存储左右子节点，比较节省空间。单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

二叉查找树

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉查找树相比散列表的优势：

  1. 散列表是无序的，二叉查找树中序遍历可输出有序。
  2. 散列表需要扩容。
  3. 在冲突较严重的情况下，散列表性能不稳定。
  4. 散列表的构造比二叉树复杂，要考虑散列函数、扩容、缩容、冲突解决等，而二叉树只需要考虑平衡性。
  5. 由于装载因子的存在，散列表较为消耗空间。

平衡二叉树

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于1。

平衡二叉查找树

结合平衡树和查找树的二叉树就是平衡查找二叉树了。 平衡二叉查找树是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。

最先被发明的平衡二叉查找树是AVL树，它严格符合平衡二叉查找树的定义。

在工程中，红黑树要比AVL树更加常用。红黑树不是严格的平衡树。它的根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。

红黑树做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比AVL树要低。

常见题目：

  1. 前中后序遍历；
  2. 层序遍历（用队列）；
  3. 按层输出（用队列，且使用两个辅助变量）；

堆

堆是一种特殊的数，满足以下两个条件的树可以称之为堆：

  1. 堆是一个完全二叉树；
  2. 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

既然堆是完全二叉树，那么堆就适合使用数组存储。从下标为1开始，假设一个节点下标为n，那么左右两个子节点的下标分别为2n和2n+1.

堆排序可分为两个阶段：建堆和排序。堆排序的时间复杂度是O(n*logn)

建堆：可以采用从下至上的插入数据的方法，假设刚开始数组里只有一个元素，每次往里插入一个元素，然后堆化。

排序：可以采用从上至下的删除数据的方法，将堆顶数据与最末尾的数据交换，然后重新堆化。

在工程中，堆排序没有快速排序快，有以下原因：

  1. 堆排序是跳着访问元素的，对CPU缓存不友好；
  2. 由于堆排序需要建堆，建堆后的数据可能比之前更加无序。所以堆排序需要的交换次数会大于快速排序

优先级队列是堆的一个应用方向。Java中PriorityQueue就是基于堆实现的。

常见题目：

  1. topK

    维护一个大小为K的堆，每次新来数据就堆化数组，每次插入时间复杂度为O(logn)，取topK时间复杂度为O(1)（需要区别Partition方法的求第K大数）。

  2. 数据流的中位数

    不仅仅可以求中位数，只要改变两个堆中的数据比例，就可以求类似“接口99响应时间”等问题了。

  3. 合并有序小文件

    有100个小文件，每个文件的大小是100MB，每个文件中存储的都是有序的字符串。希望将这些100个小文件合并成一个有序的大文件。

字符串匹配

单模式匹配

BF算法

BF算法中的BF是Brute Force，暴力匹配。时间复杂度是O(n*m)，其中n是主串长度，m是模式串长度。

BF算法简单简单朴素，效率低，但在实际开发中却较为常用。因为实际使用场景下，一般的字符串都比较小，选用BF效率影响不大。且BF算法简单不易出错。

RK算法

RK算法的全称叫Rabin-Karp算法，是由它的两位发明者Rabin和Karp的名字来命名的。

RK算法的思路是这样的：我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。哈希算法的选择很重要，理想情况下，时间复杂度是O(n)，n为主串长度。

BM算法

BM（Boyer-Moore）算法是一种非常高效的字符串匹配算法，在工程非常常用。有实验统计，它的性能是著名的KMP算法的3到4倍。我们可以在BF算法的基础上理解BM算法。

在BF算法中，模式串在匹配失败后会往后移动一位。BM算法就是找到规律，让模式串每次多往后移动几位，减少不必要的字符比较。

BM算法的时间复杂度分析起来是非常复杂，这篇论文“Tight bounds on the complexity of the Boyer-Moore string matching algorithm”证明了在最坏情况下，BM算法的比较次数上限是3n。

常见题目：文本编辑器的查找功能。

KMP

KMP算法是根据三位作者（D.E.Knuth，J.H.Morris和V.R.Pratt）的名字来命名的。KMP算法的核心思想，跟BM算法非常相近。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位。

KMP算法的时间复杂度就是O(m+n) 。

多模式匹配

Trie树

Trie树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构， 用来解决在一组字符串集合中快速查找某个字符串的问题。Trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。构建Tire树的时间复杂度是O(m)，m表示所有字符串的长度和。

将多个模式串构建成Tire树。Tire树构建完成后，就可以用主串来走这个Tire树了。时间复杂度为O(n)，n为要查询的主串长度。

Tire的存储是比较浪费空间的，我们需要在效率和空间中找到平衡。

实际上，字符串的匹配问题，笼统上讲，其实就是数据的查找问题。对于支持动态数据高效操作的数据结构，比如散列表、红黑树、跳表等等。这些数据结构也可以实现在一组字符串中查找字符串的功能。我们拿散列表和红黑树，跟Trie树比较一下。Tire树对多个模式串有一定的要求，若不满足以下要求，Tire树的空间消耗会比较大：

  1. 字符串中包含的字符集尽量要小；

  2. 字符串的前缀重合尽量要多。

Trie树更加适合查找前缀匹配的字符串问题。散列表或者红黑树更加适合精确匹配查找问题。

常见题目：

  1. 手机英文输入自动提示单词（ACM题目：POJ1451 T9 http://poj.org/problem?id=1451）；
  2. 搜索引擎的搜索关键词提示功能

AC自动机

AC自动机算法，全称是Aho-Corasick算法。其实，Trie树跟AC自动机之间的关系，就像单串匹配中朴素的串匹配BF算法，跟KMP算法之间的关系一样。AC自动机实际上就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上罢了。AC自动机适合大量文本中多模式串的精确匹配查找，时间复杂度可以到O(n*len)。len是模式串的平均长度。

常见题目：论坛中的敏感词过滤。

动态数据结构：散列表、二叉树、跳表

贪心算法

分治算法

子问题之间没有相关性

常见题目：求逆序对数量（借助归并排序）

回溯算法

回溯是一种在一组可能的解中，找到符合要求解的算法。剪枝操作可以增加回溯的效率。

常见问题：深度优先遍历、01背包、8皇后、旅行商问题、全排列等。

位运算

二进制1的个数（n&(n-1)）

二分查找

杨氏矩阵是否存在某树（leetcode 74）

单峰值数组寻找峰值

多峰值数组寻找峰值

双指针

字符串翻转（单词，旋转）

堆

数据流中位数

DFS

二维矩阵中找字符串，不能重复（leetcode 79）

全排列

二叉树

  1. 二叉树深度（leetcode 104后序遍历）

  2. 判断是否平衡二叉树（leetcode 110后序遍历）

  3. 判断是否为另一棵树的子结构（leetcode 572）

  4. 判断是否镜像树（leetcode 101）

  5. 二叉树的最大直径（与深度有关）

  6. 合并二叉树

  7. 求两个节点的最低公共祖先（leetcode 236）

  8. 前中后序遍历

  9. 中序遍历的下一个节点（优先考虑右子树最左节点，若不存在，则考虑父节点）

链表

  1. 判断是否单链表回文
  2. 奇偶链表反转
  3. 两个链表的第一个交叉点（交换遍历）

Bit Map

  1. 使用10MB内存，找出40亿个整数的中位数
  2. 40亿个非负整数中找到出现两次的数
  3. 40亿个非负整数中找到没出现的数

数组

连续子数组的最大和（DP）

下一个排列

  1. 范围[1,n]共n+1个数，找唯一一个重复的数（使用环检测）
  2. 范围[0,n-1]共n个数，找重复的数（下标位置互换）
  3. 滑动窗口中的最大值
  4. 数组中找第K大的数（使用快排中的partition，O(n)，特例：找出出现次数超过一半的数，计数法？）
  5. 数组中找出TopK（1.使用partition，会修改数组；2.使用堆O(n*logk)，不会修改数组，适合大数据）
  6. 某数字在排序数组中出现的次数（两次二分查找找头尾，O(logn)）
  7. 数组中只出现一次的数/数组中出现两次的数（使用异或位运算）