面试中你应该知道的数据结构与算法

On By 汴梁書僮In 技术

之前每次准备面试的时候都会过一遍算法与数据结构，但一直没有一份固定的资料，系统的过一遍算法书不太现实，每次都是现找，最近群里在讨论面试的事儿。今年受covid影响，毕业生不好找工作，借着之前的面试笔记，整理出此篇，希望可以帮到大家。

注：所有图片均非原创，侵权删，引用声明在文末。

注：持续更新

队，栈，堆，链表，数组这些就不再赘述了

排序

wiki比我总结的好。。。

排序算法

Union find并查集

并查集主要两个操作

  • Find：确定元素是哪个子集
  • Union：合并

并查集用树建模，确定两个元素是否在同一子集，就是看是否有同一个的root，建树的过程就是遍历所有node，如果相连，便归为同一子集

优化1: 平衡树，当往树的某一边一直添加node，会导致不平衡树，最坏的情况是线性树，也就丧失了树的优越性，优化方法就是将每个节点加上权值，即每个节点下有多少子节点，如果一遍权值过重就把过重边的node作为root，从而让树平衡。

优化2: 让树扁平化，当树深度增加，就会导致回溯寻根的过程加长，解决办法就是当遍历到某节点，发现更浅层的根，便把当前节点的根指向浅层节点。从而让树扁平化

适用问题：

Priority queue优先队列

队是先进先出，优先队列就是优先级最高的先出列（最大或最小）

一般用堆实现，堆是一种特殊的树，父节点优先于（大于或小于）子节点，从而实现优先队列。最经典的做法就是二叉堆，一般可以用数组实现，父节点就是k/2，子节点就是2k和2k+1

优先队列的操作一般是：插入，删除节点。基本做法就是，如果子节点和父节点优先等级发生变化就交换，所以殊途同归，操作就是上游和下沉。时间复杂度就是logn

一种优化是d叉树，几个叉取决于d的值

优先队列最常见的应用就是堆排序，建堆的过程就是从队末遍历节点往上冒泡，然后往上冒泡，然后每次pop根节点，调整树，repeat！

堆排序的时间复杂度是O（nlogn + n）～= O（nlogn）

Binary Search Tree二叉搜索树

  • 左子树节点小于根节点
  • 右子树节点大于等于跟节点
  • 左子树，右子树也是搜索二叉树

经典问题：

所有操作遵循小了向左，大了向右。

能做的优化和前边一样，让树平衡，记录子树大小。不再赘述。

比较有意思的是删除节点的算法，三种情况：

  • 没有子节点，直接删除就好
  • 一个子节点，直接删除，用子节点代替父节点
  • 两个子节点，用右子树的最小节点代替要删除节点，用数学证明一下就好，很简单

2-3树

2-3树有两种节点，双子节点和三子节点。2-3树有两个特质：

  • 有序遍历会生成密匙
  • 完美平衡：从root到每个子节点深度相等

几种常见操作：

  • 搜索：这个比较简单，如果是单节点就直接比较，如果是区间节点就按区间比较
  • 插入比较复杂，分双子节点和三子节点：
    • 双子节点：直接插入双子节点变成三子节点
    • 三子节点：
      • 新值插入到三子节点，变成一个四子节点， 把四子节点的中间值插入到父节点中，然后迭代循环，一直到满足条件为止，如果到了跟节点依然是四子节点，就分成两个双子节点。

四子节点变三子节点基本变形如下

红黑树

红黑树其实是一种特殊的2-3树，用红黑节点分别代表2，3节点。从2-3树转换到红黑树：

红黑树的特质：

  • 根节点是黑色
  • 叶子节点是黑色
  • 每个红色结点的两个子结点一定都是黑色
  • 任意一结点到每个叶子结点的路径都包含数量相同的黑结点（人称黑色完美平衡）如下图所示，P的左子树和右子树黑色节点层数相同，即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点

红黑树有两种构成方式，一种是传统红黑树，通过节点染色实现;

一种是红黑树的变体，左倾红黑树，通过边染色实现，保证复杂度相同的前提下，更容易用代码实现。

为了保证红黑树的完美平衡，基本操作有

  • 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变
  • 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
  • 变色：结点的颜色由红变黑或由黑变红。

下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：

但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：

此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：

左旋，右旋，变色主要用在插入和删除节点后保持红黑树的平衡。

插入：

首先要找到插入位置，和搜索二叉树一样，不再赘述；

然手就是插入节点，那么插入节点是什么颜色呢？是红色，理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

然后从子节点向上通过左旋， 右旋，变色调节平衡，以下图为例，插入节点21

我们以刚才插入节点21的情况为例：

首先，我们需要做的是变色，把节点25及其下方的节点变色：

此时节点17和节点25是连续的两个红色节点，为了维持红黑树的规则，我们把节点8和节点17进行变色，由红色节点编程黑色节点。这样以来就形成了新的红黑树：

可以看出，红黑树与搜索二叉树不同，是自下向上生长的。当然你要考虑各种情况，叔，父，根，子，叶，但万变不离其宗。

红黑树删除

分三种情景：

  • 情景1：若删除结点无子结点，直接删除
  • 情景2：若删除结点只有一个子结点，用子结点替换删除结点
  • 情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点

删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点

基于此，上面所说的3种二叉树的删除情景可以相互转换并且最终都是转换为情景1！

  • 情景2：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为情景3，一直自顶向下转换，总是能转换为情景1。（对于红黑树来说，根据性质5.1，只存在一个子结点的结点肯定在树末了）
  • 情景3：删除结点用后继结点（肯定不存在左结点），如果后继结点有右子结点，那么相当于转换为情景2，否则转为为情景1。

左倾红黑树与普通二叉树类似：

左旋：

右旋：

染色：

左倾红黑树的插入操作（类比之前的2-3树）：

插入单节点：

插入双节点

插入到一个双节点树：

插入到一个三节点树：

插入一个三节点：

最后补充，Java的HashMap和TreeMap都用到了红黑树，感兴趣的可以去看源代码/:X-)

B树

B树是一种自平衡二叉树，常用于数据库中（比如MySql），数据库充分利用磁盘快的原理，把节点大小限制和充分适用磁盘块大小范围，把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。B树的定义：

  • 排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
  • 子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
  • 关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
  • 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

B树的插入，有两种方法，一种自下而上的，一种自上而下的，说不上哪个好，自己体会：

自上而下：

定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

遵循规则：

（1）节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；

（2）排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;

自下而上：

Trie前缀树，又称字典树

用于保存关联数组，字符串，电话号码本

每个节点保存字符，每个节点有n个子节点

搜索的话就一直深搜到Null节点，插入删除就是深搜

例题：https://leetcode.com/explore/featured/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3329/

Solution：https://github.com/RuochenLI/Leetcode/blob/master/src/main/java/challenge/year2020/may/Trie.java

后缀树

//Todo: https://blog.csdn.net/v_JULY_v/article/details/6897097

最小生成树MINIMUM SPANNING TREES

最小生成树的定义：

  • 相连
  • 无环
  • 连接所有节点

给一个有权无向图，求最小生成树

最简单粗暴的方法，当然是硬搜，good luck～

切分定理：在一幅连通加权无向图中，如有一条横切边的权值严格小于所有其他横切边，则这条边必然属于图的最小生成树。

证明：
令e为权重最小的横切边，假设T为图的最小生成树，且T不包含e。那么如果将e加入T，得到的图必然含有一条经过e的环，且这个环也含有另一条横切边–设为{\displaystyle e'}，{\displaystyle e'}的权重必然大于e，那么用e替换{\displaystyle e'}可以形成一个权值小于T的生成树，与T为最小生成树矛盾。所以假设不成立

基于切分定理的贪心算法：

  • 所有边染色为灰色
  • 找到最小的灰色的切分，染色为黑色（注意避免回路，否则就不是切分）
  • 重复V-1次

Kruskal算法

和上边的贪心算法类似，按照边的权重顺序（从小到大）将边加入生成树中，但是若加入该边会与生成树形成环则不加入该边。直到树中含有V-1条边为止。这些边组成的就是该图的最小生成树。Kruskal算法的时间复杂度为{\displaystyle E\log E}

Prime算法

其实。。。依然是贪心，从0节点开始生成树，每次总是添加生长中的树和树中除该生长的树以外的部分形成的切分的具有最小权值的横切边，重复V-1次，Prim算法的时间复杂度为{\displaystyle O(E+V\log V)}。

最短路径

提到最短路径，最先想到的就是Dijkstra和Floyd

Dijkstra算法

狄杰斯特拉的基本思想是，选定起点，每次选出起始节点到各个未通节点最短的一条路径，加入图中，更新起始节点到各个未通节点的距离。具体操作步骤如下：

  1. 两个集合S和U，S用来记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)
  2. 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”
  3. 从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。
  4. 更新U中各个顶点到起点s的距离
  5. 重复3，4
Bellman-Ford算法

Djkstra不适用于负边的情况，因为负边会让已经生成的最短路径更小，于是便有了Bellman-Ford算法。Bellman-Ford算法与Dijkstra类似，区别在于，狄杰斯特拉以贪心算法选取未被处理的具有最小权值的节点，然后对他进行松弛操作（即dis(i,j) = max(dis(i,j), dis(i,k) + dis(k,j)）；而Bellman-Ford算法会对所有边进行松弛操作。为代码

procedure BellmanFord(list vertices, list edges, vertex source)
   // 读入边和节点的列表并对distance和predecessor写入最短路径
   // 初始化图
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null
   // 对每一条边重复操作
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u
   // 检查是否有赋权重的回路：存在经过（V-1）次遍历后仍可以松弛的边
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "图包含赋权重的回路"
Floyd算法

弗洛伊德的算法就是动态规划的思想，寻找从i到j的最短路径，无外乎就是从i直接到j，或者通过k到j，所以算术表达式为：

dis(i,j) = max(dis(i,j), dis(i,k) + dis(k,j)

算法描述：

let dist be a |V| × |V| array of minimum distances initialized to ∞ 
for each vertex v
   dist[v][v] ← 0
for each edge (u,v)
   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][j] > dist[i][k] + dist[k][j] 
            dist[i][j] ← dist[i][k] + dist[k][j]
        end if

最大网络流

简而言之，就是在有向加权图中，从S到T可流过的最大流量。

弗洛伊德算法

找到一条从S到T的可行路线分两步：

  • 找到一条还可以提升流量的边，提升到最大流量
  • 如果下游行不通，找到一条已有流量的边，逆向减去当前流量

重复循环直到从S到T

  • 正向边被填满
  • 或者逆向边为空

拓扑排序（Topological Sorting）

是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

  1. 每个顶点出现且只出现一次。
  2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

检测是否有环，DFS，对每个节点进行标记。

算法——贪心：

  1. 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
  2. 从图中删除该顶点和所有以它为起点的有向边。
  3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

字符串搜索：Boyer-Moore算法

概括来讲，Boyer-Moore算法预先构建了一个好词缀和坏词缀规则表，”字符串”与”搜索词”头部对齐，从尾部开始比较。

每次遇到坏字符，

字符串后移位数=max（坏字符的位置 – 坏字符在搜索词中的上一次出现位置，好后缀的位置 -好后缀搜索词中的上一次出现位置）

具体详解摘自自阮一峰老师的博客：

1.

假定字符串为”HERE IS A SIMPLE EXAMPLE”，搜索词为”EXAMPLE”。

2.

首先，”字符串”与”搜索词”头部对齐，从尾部开始比较。

这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符（整体上）肯定不是要找的结果。

我们看到，”S”与”E”不匹配。这时，“S”就被称为”坏字符”（bad character），即不匹配的字符。我们还发现，”S”不包含在搜索词”EXAMPLE”之中，这意味着可以把搜索词直接移到”S”的后一位。

3.

依然从尾部开始比较，发现”P”与”E”不匹配，所以”P”是”坏字符”。但是，”P”包含在搜索词”EXAMPLE”之中。所以，将搜索词后移两位，两个”P”对齐。

4.

我们由此总结出“坏字符规则”：

　　后移位数 = 坏字符的位置 – 搜索词中的上一次出现位置

如果”坏字符”不包含在搜索词之中，则上一次出现位置为 -1。

以”P”为例，它作为”坏字符”，出现在搜索词的第6位（从0开始编号），在搜索词中的上一次出现位置为4，所以后移 6 – 4 = 2位。再以前面第二步的”S”为例，它出现在第6位，上一次出现位置是 -1（即未出现），则整个搜索词后移 6 – (-1) = 7位。

5.

依然从尾部开始比较，”E”与”E”匹配。

6.

比较前面一位，”LE”与”LE”匹配。

7.

比较前面一位，”PLE”与”PLE”匹配。

8.

比较前面一位，”MPLE”与”MPLE”匹配。我们把这种情况称为”好后缀”（good suffix），即所有尾部匹配的字符串。注意，”MPLE”、”PLE”、”LE”、”E”都是好后缀。

9.

比较前一位，发现”I”与”A”不匹配。所以，”I”是”坏字符”。

10.

根据”坏字符规则”，此时搜索词应该后移 2 – （-1）= 3 位。问题是，此时有没有更好的移法？

11.

我们知道，此时存在”好后缀”。所以，可以采用“好后缀规则”：

　　后移位数 = 好后缀的位置 – 搜索词中的上一次出现位置

举例来说，如果字符串”ABCDAB”的后一个”AB”是”好后缀”。那么它的位置是5（从0开始计算，取最后的”B”的值），在”搜索词中的上一次出现位置”是1（第一个”B”的位置），所以后移 5 – 1 = 4位，前一个”AB”移到后一个”AB”的位置。

再举一个例子，如果字符串”ABCDEF”的”EF”是好后缀，则”EF”的位置是5 ，上一次出现的位置是 -1（即未出现），所以后移 5 – (-1) = 6位，即整个字符串移到”F”的后一位。

这个规则有三个注意点：

　　（1）”好后缀”的位置以最后一个字符为准。假定”ABCDEF”的”EF”是好后缀，则它的位置以”F”为准，即5（从0开始计算）。

　　（2）如果”好后缀”在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，”EF”在”ABCDEF”之中只出现一次，则它的上一次出现位置为-1（即未出现）。

　　（3）如果”好后缀”有多个，则除了最长的那个”好后缀”，其他”好后缀”的上一次出现位置必须在头部。比如，假定”BABCDAB”的”好后缀”是”DAB”、”AB”、”B”，请问这时”好后缀”的上一次出现位置是什么？回答是，此时采用的好后缀是”B”，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个”好后缀”只出现一次，则可以把搜索词改写成如下形式进行位置计算”(DA)BABCDAB”，即虚拟加入最前面的”DA”。

回到上文的这个例子。此时，所有的”好后缀”（MPLE、PLE、LE、E）之中，只有”E”在”EXAMPLE”还出现在头部，所以后移 6 – 0 = 6位。

12.

可以看到，”坏字符规则”只能移3位，”好后缀规则”可以移6位。所以，Boyer-Moore算法的基本思想是，每次后移这两个规则之中的较大值。

更巧妙的是，这两个规则的移动位数，只与搜索词有关，与原字符串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。

13.

继续从尾部开始比较，”P”与”E”不匹配，因此”P”是”坏字符”。根据”坏字符规则”，后移 6 – 4 = 2位。

14.

从尾部开始逐位比较，发现全部匹配，于是搜索结束。如果还要继续查找（即找出全部匹配），则根据”好后缀规则”，后移 6 – 0 = 6位，即头部的”E”移到尾部的”E”的位置。

最大子序列

最大子序列是一道经典的算法题，LeetCode原题：https://leetcode.com/problems/maximum-subarray/

原理是基于动态规划的Kadane算法。代码描述如下：

public int maxSubArray(int[] nums) {
    int max = Integer.MIN_VALUE;
    int subsum = 0;
    for (final int item : nums) {
        subsum = item + Math.max(subsum, 0);
        max = Math.max(subsum, max);
    }
    return max;
}

比较难理解的部分应该是Math.max(subsum, 0)，其实也不难理解，任何一个最大子序列的和，第一位绝对不会是负数，根据贪心算法，如果为负，就设为0 重新计算。 根据最大子序列的原型变形题是环形数组最大子序列, LeetCode原题

https://leetcode.com/problems/maximum-sum-circular-subarray/

环形数组的最大子序列是建立在最大子序列算法之上的，分三种情况：

  • 如果数组全部是正数，最大子序列就是Sum
  • 如果数组中有正有负，分两种情况，跨越边界和没有跨越边界
    • 没有跨越边界：直接求最大子数组
    • 跨越边界：求数组和，再减去数组中的子数组最小和（最小和一定是负数）
    • 最后求无边界和有边界中max最大的
  • 如果数组全部为负，那最大的就是数组中最大的负数，这个和第一种情况一样可以直接由Kadane算法算出

代码如下：

        if (A == null || A.length < 1) {
            return 0;
        }
        int curMax = A[0];
        int max = A[0];
        int curMin = A[0];
        int min = A[0];
        int sum = A[0];
        for (int i = 1; i < A.length; i++) {
            sum += A[i];
            curMax = A[i] + Math.max(curMax, 0);
            max = Math.max(curMax, max);
            curMin = A[i] + Math.min(curMin, 0);
            min = Math.min(curMin, min);
        }
        if (max < 0)
            return max;
        return Math.max(sum - min, max);

写在最后的

引用 Max Howell的一条有名的twitter:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

Reference：

该博客用于非商业用途，侵权删

https://zhuanlan.zhihu.com/p/27700617

Leetcode.com

https://algs4.cs.princeton.edu/lectures/

https://www.jianshu.com/p/e136ec79235c

https://zhuanlan.zhihu.com/p/31805309

wikipedia.org

http://www.ruanyifeng.com/

发表评论

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 ( 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 ( 注销 /  更改 )

取消

Connecting to %s