［经典］技术面试宝典：很全面的算法和数据结构知识（含代码）

我就是我 2022-06-12 01:30 118阅读 0赞

本文汇总了技术面试时需要了解的算法和数据结构知识。

数据结构部分

链表

*  链表是一种由节点（Node）组成的线性数据集合，每个节点通过指针指向下一个节点。它是一种由节点组成，并能用于表示序列的数据结构。
 *  单链表：每个节点仅指向下一个节点，最后一个节点指向空（null）。
 *  双链表：每个节点有两个指针p，n。p指向前一个节点，n指向下一个节点；最后一个节点指向空。
 *  循环链表：每个节点指向下一个节点，最后一个节点指向第一个节点。
 *  时间复杂度：
    
     *  索引：O(n)
     *  查找：O(n)
     *  插入：O(1)
     *  删除：O(1)

栈

*  栈是一个元素集合，支持两个基本操作：push用于将元素压入栈，pop用于删除栈顶元素。
 *  后进先出的数据结构（Last In First Out, LIFO）
 *  时间复杂度
    
     *  索引：O(n)
     *  查找：O(n)
     *  插入：O(1)
     *  删除：O(1)

队列

*  队列是一个元素集合，支持两种基本操作：enqueue 用于添加一个元素到队列，dequeue 用于删除队列中的一个元素。
 *  先进先出的数据结构（First In First Out, FIFO）。
 *  时间复杂度
    
     *  索引：O(n)
     *  查找：O(n)
     *  插入：O(1)
     *  删除：O(1)

树

*  树是无向、联通的无环图。

二叉树

*  二叉树是一个树形数据结构，每个节点最多可以有两个子节点，称为左子节点和右子节点。
 *  满二叉树（Full Tree）：二叉树中的每个节点有 0 或者 2 个子节点。
 *  完美二叉树（Perfect Binary）：二叉树中的每个节点有两个子节点，并且所有的叶子节点的深度是一样的。
 *  完全二叉树：二叉树中除最后一层外其他各层的节点数均达到最大值，最后一层的节点都连续集中在最左边。

二叉查找树

*  二叉查找树（BST）是一种二叉树。其任何节点的值都大于等于左子树中的值，小于等于右子树中的值。
 *  时间复杂度
    
     *  索引：O(log(n))
     *  查找：O(log(n))
     *  插入：O(log(n))
     *  删除：O(log(n))

![ecdb15891e2d452fb45787c6e382298f_th.jpg][]

字典树

*  字典树，又称为基数树或前缀树，是一种用于存储键值为字符串的动态集合或关联数组的查找树。树中的节点并不直接存储关联键值，而是该节点在树中的位置决定了其关联键值。一个节点的所有子节点都有相同的前缀，根节点则是空字符串。

![15fd50651dd44827ad69e0d75067edb8_th.jpg][]

树状数组

*  树状数组，又称为二进制索引树（Binary Indexed Tree，BIT），其概念上是树，但以数组实现。数组中的下标代表树中的节点，每个节点的父节点或子节点的下标可以通过位运算获得。数组中的每个元素都包含了预计算的区间值之和，在整个树更新的过程中，这些计算的值也同样会被更新。
 *  时间复杂度
    
     *  区间求和：O(log(n))
     *  更新：O(log(n))

![39e6770b862445ca9d872bcd43fb4b9c_th.jpg][]

线段树

*  线段树是用于存储区间和线段的树形数据结构。它允许查找一个节点在若干条线段中出现的次数。
 *  时间复杂度
    
     *  区间查找：O(log(n))
     *  更新：O(log(n))

![83632e4453b04f1f8d25a2f89bb02fd4_th.jpg][]

堆

*  堆是一种基于树的满足某些特性的数据结构：整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中，父节点的键值永远大于等于所有子节点的键值，根节点的键值是最大的。最小堆中，父节点的键值永远小于等于所有子节点的键值，根节点的键值是最小的。
 *  时间复杂度
    
     *  索引：O(log(n))
     *  查找：O(log(n))
     *  插入：O(log(n))
     *  删除：O(log(n))
     *  删除最大值/最小值：O(1)

![8f8ae68980cc4ae5bcae49ea4756fa97_th.jpg][]

哈希

*  哈希用于将任意长度的数据映射到固定长度的数据。哈希函数的返回值被称为哈希值、哈希码或者哈希。如果不同的主键得到相同的哈希值，则发生了冲突。
 *  Hash Map：hash map 是一个存储键值间关系的数据结构。HashMap 通过哈希函数将键转化为桶或者槽中的下标，从而便于指定值的查找。
 *  冲突解决
    
     *  链地址法（Separate Chaining）：在链地址法中，每个桶（bucket）是相互独立的，每一个索引对应一个元素列表。处理HashMap 的时间就是查找桶的时间（常量）与遍历列表元素的时间之和。
     *  开放地址法（Open Addressing）：在开放地址方法中，当插入新值时，会判断该值对应的哈希桶是否存在，如果存在则根据某种算法依次选择下一个可能的位置，直到找到一个未被占用的地址。开放地址即某个元素的位置并不永远由其哈希值决定。

![c2406f31cd9c4a94b49c2c384f0d6ed3_th.jpg][]

图

![0b26f1ae06d44bca9f6720d479df00d4_th.jpg][]

![457a6638b85446fe81e3ba8699fadfb7_th.jpg][]

算法部分

排序

快速排序

*  稳定：否
 *  时间复杂度
    
     *  最优：O(nlog(n))
     *  最差：O(n^2)
     *  平均：O(nlog(n))

![95cfa94341f94d07b28233dd9fd44690_th.jpg][]

合并排序

*  合并排序是一种分治算法。这个算法不断地将一个数组分为两部分，分别对左子数组和右子数组排序，然后将两个数组合并为新的有序数组。
 *  稳定：是
 *  时间复杂度：
    
     *  最优：O(nlog(n))
     *  最差：O(nlog(n))
     *  平均：O(nlog(n))

桶排序

![f49aecac5f844a9896ae2256669f3ddf.jpg][]

![a0d3265eb76d4e178839a15d5b3c3fdb_th.jpg][]

![3ca3ebe503db4dd98998aa5c3faa3f2d_th.jpg][]

图算法

深度优先搜索

*  深度优先搜索是一种先遍历子节点而不回溯的图遍历算法。
 *  时间复杂度：O(|V| + |E|)

![fadcd50807754c64bf7f330052b5ea6b_th.jpg][]

广度优先搜索

*  广度优先搜索是一种先遍历邻居节点而不是子节点的图遍历算法。
 *  时间复杂度：O(|V| + |E|)

![3fb21709cef74a5192a435b6d612b180_th.jpg][]

![0046c224944740988351eed564aa8133_th.jpg][]

![3a85cdf867244280a0aae522818f13bb_th.jpg][]

![d95708c99c8a487387ce84d9eb2337cb_th.jpg][]

![317f71fca82845cfbda2dc955ae8a878_th.jpg][]

Floyd-Warshall 算法

*  Floyd-Warshall 算法是一种在无环带权图中寻找任意节点间最短路径的算法。
 *  该算法执行一次即可找到所有节点间的最短路径（路径权重和）。
 *  时间复杂度：
    
     *  最优：O(|V|^3)
     *  最差：O(|V|^3)
     *  平均：O(|V|^3)

最小生成树算法

*  最小生成树算法是一种在无向带权图中查找最小生成树的贪心算法。换言之，最小生成树算法能在一个图中找到连接所有节点的边的最小子集。
 *  时间复杂度：O(|V|^2)

![ba5c1179dfc5442993fa0134ff23c8f1.jpg][]

Kruskal 算法

*  Kruskal 算法也是一个计算最小生成树的贪心算法，但在 Kruskal 算法中，图不一定是连通的。
 *  时间复杂度：O(|E|log|V|)

![e81ce4226ccf4654934a2f997b60c19a.jpg][]

贪心算法

*  贪心算法总是做出在当前看来最优的选择，并希望最后整体也是最优的。
 *  使用贪心算法可以解决的问题必须具有如下两种特性：
    
     *  最优子结构
        
         *  问题的最优解包含其子问题的最优解。
     *  贪心选择
        
         *  每一步的贪心选择可以得到问题的整体最优解。
 *  实例-硬币选择问题

![49487c5593894cf6a8d705ee0e731e61_th.jpg][]

位运算

*  位运算即在比特级别进行操作的技术。使用位运算技术可以带来更快的运行速度与更小的内存使用。
 *  测试第 k 位：s & (1 << k);
 *  设置第k位：s |= (1 << k);
 *  关闭第k位：s &= ~(1 << k);
 *  切换第k位：s ^= (1 << k);
 *  乘以2n：s << n;
 *  除以2n：s >> n;
 *  交集：s & t;
 *  并集：s | t;
 *  减法：s & ~t;
 *  提取最小非0位：s & (-s);
 *  提取最小0位：~s & (s + 1);
 *  交换值：x ^= y; y ^= x; x ^= y;

运行时分析

大 O 表示

*  大 O 表示用于表示某个算法的上界，用于描述最坏的情况。

![7e6af813924f4edaa4ec3eb29120b041_th.jpg][]

小 O 表示

*  小 O 表示用于描述某个算法的渐进上界，二者逐渐趋近。

大 Ω 表示

*  大 Ω 表示用于描述某个算法的渐进下界。

![2b49985faae84ebdb5bf1d5c79354957_th.jpg][]

小 ω 表示

*  小 ω 表示用于描述某个算法的渐进下界，二者逐渐趋近。

Theta Θ 表示

*  Theta Θ 表示用于描述某个算法的确界，包括最小上界和最大下界。

![a8c3452135be4422a2f8f67d10a939bc_th.jpg][]

以为这就结束了？No，还有 LeetCode 题目的参考解答代码

Java 代码目录如下：

![8c0434e09fcd464db3307f15d85939bf_th.jpg][]

![dcd6228fdd0e45e18556759a53d276db.jpg][]

[ecdb15891e2d452fb45787c6e382298f_th.jpg]: /images/20220612/8c1330b1e4c04bc88bce42a250ace548.png
[15fd50651dd44827ad69e0d75067edb8_th.jpg]: /images/20220612/7e1abe3b444b4e12b5b41996b3060e42.png
[39e6770b862445ca9d872bcd43fb4b9c_th.jpg]: /images/20220612/0dcbacffb8c347649eec90b79ff18bd3.png
[83632e4453b04f1f8d25a2f89bb02fd4_th.jpg]: /images/20220612/c54161193e83426aa9b55d82a265a0f1.png
[8f8ae68980cc4ae5bcae49ea4756fa97_th.jpg]: /images/20220612/ceec7300ea074e598a474c29974fe49b.png
[c2406f31cd9c4a94b49c2c384f0d6ed3_th.jpg]: /images/20220612/37321712cf03465882ee219152fd4725.png
[0b26f1ae06d44bca9f6720d479df00d4_th.jpg]: /images/20220612/efefae5a9c564b4a8df3b7188f3d8db0.png
[457a6638b85446fe81e3ba8699fadfb7_th.jpg]: /images/20220612/2e0abd2ebe284755b1852bfefd593458.png
[95cfa94341f94d07b28233dd9fd44690_th.jpg]: /images/20220612/30395e21e8fa4961a2579bcc7303c1f9.png
[f49aecac5f844a9896ae2256669f3ddf.jpg]: /images/20220612/14518f9ca7b847ecbfd7c79ca45884fd.png
[a0d3265eb76d4e178839a15d5b3c3fdb_th.jpg]: /images/20220612/b1c697e2b65240b1ba2401995cdd6803.png
[3ca3ebe503db4dd98998aa5c3faa3f2d_th.jpg]: /images/20220612/31f561301eb7455d87faad963572acd4.png
[fadcd50807754c64bf7f330052b5ea6b_th.jpg]: /images/20220612/fa9a8e042bd24dd3878abf961f090d59.png
[3fb21709cef74a5192a435b6d612b180_th.jpg]: /images/20220612/7cbd73e715994a30ab6b268e9605de5e.png
[0046c224944740988351eed564aa8133_th.jpg]: /images/20220612/50e30d3e7ab944729902cf3c4f363e13.png
[3a85cdf867244280a0aae522818f13bb_th.jpg]: /images/20220612/2e9475eaa4f640baa15ce5e1819746bb.png
[d95708c99c8a487387ce84d9eb2337cb_th.jpg]: /images/20220612/a87bee5353e04f6cba05b8fbfd328e80.png
[317f71fca82845cfbda2dc955ae8a878_th.jpg]: /images/20220612/7b0a2c69a9ac4e11a66468fc81e9213e.png
[ba5c1179dfc5442993fa0134ff23c8f1.jpg]: /images/20220612/e87c68ee1c1a490ead5526a65bd9834e.png
[e81ce4226ccf4654934a2f997b60c19a.jpg]: /images/20220612/915a1917f7cd494a8d81b106d58051b6.png
[49487c5593894cf6a8d705ee0e731e61_th.jpg]: /images/20220612/24f6ce58e983445ea6ba107d8df6aeb1.png
[7e6af813924f4edaa4ec3eb29120b041_th.jpg]: /images/20220612/5a1e844aa77d4ef3b8dcf7d704a80d7c.png
[2b49985faae84ebdb5bf1d5c79354957_th.jpg]: /images/20220612/8151a49488f349e8b0566b9331e35df5.png
[a8c3452135be4422a2f8f67d10a939bc_th.jpg]: /images/20220612/ec743b001008429f8f90d29a3288f3f2.png
[8c0434e09fcd464db3307f15d85939bf_th.jpg]: /images/20220612/d0ddb66a967847b0a3d3d1d8c1ff3c99.png
[dcd6228fdd0e45e18556759a53d276db.jpg]: /images/20220612/ef656c7f481141a3841c764f418f673d.png