广度优先搜索可解决两类问题：
第一类问题：从节点A出发，又前往节点B的路径吗？(在你的交际关系网中，有芒果销售商吗？)
第二类问题：从节点A出发，前往节点B的哪条路径最短？(哪个芒光销售商与你的关系最近？)

不管是广度优先遍历一幅有意图还是一棵树，都要用到队列。
首先把起始节点(对树而言是根节点)放入队列。接下来每次从队列的头部取出一个节点，遍历这个节点之后
把它能到达的节点(对树而言是子节点)都依次放入队列。
重复一个队列问题，直到队列中的节点全部被遍历为止。

如果你要找出最快的路径，需要使用另外一种算法。狄克斯特拉算法

狄克斯特拉算法：

1. 找出”最便宜”的节点，即可在最短时间内到达的节点。
2. 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
3. 重复这个过程，直到对图中的每个节点都这么做了。
4. 计算最终路径。

狄克斯特拉算法用于每条边都有关联数字的图，这些数字成为权重。
带权重的图称为加权图，不带权重的图称为非加权图。
要计算非加权图中的最短路径，可使用广度优先搜索。
要计算加权图中的最短路径，可使用狄克斯特拉算法。
狄克斯特拉算法只适用于有向无环图。
贝尔曼-福德算法使用于图中包含负权边。

动态规划：(背包问题，旅游行程最优化)
是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题。
仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。

问题：
1.生物学家根据最长公共序列来确定DNA链的相似性，今儿判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
2.git diff命令，指出两个文件的差异，也是使用动态规划实现的。
3.字符串的相似程度。编辑距离指出了连哥哥字符串的相似程度，也是使用动态规划计算得到的。

小结：
1.需要在给定约束条件下优化某种指标时，动态规划很有用。
2.问题可分解为离散自问题时，可使用动态规划来解决。
3.每种动态规划解决方案都涉及网格。
4.单元格中的值通常就是你也要优化的值。
5.每个单元格都是一个子问题，因此需要考虑如何将问题分解为自问题。

贪婪算法：(旅行商问题，广播台问题)
贪婪算法解决问题的时候，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。

NP完全问题：
1.元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
2.涉及”所有组合”的问题通常时NP完全问题。
3.不能将问题分成小问题，必须考虑各种可能的情况。
4.如果问题涉及序列(如旅行商问题中的城市序列)且难以解决，它可能就是NP完全问题。
5.如果问题涉及集合(如广播台集合)且难以解决，它可能就是NP完全问题。
6.如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

问题：
1.有个邮递员负责给20个家庭送信，需要找出经过这20个家庭的最短路径？请问这是一个NP完全问题吗？
2.有一堆人中超出最大的朋友圈(即其中任何两个人都相识)？是NP完全问题么？
3.你要制作美国地图，需要用不同的颜色标出相邻的州。为此，你需要确定最少需要使用多少种颜色，才能保证任何两个相邻州的颜色都不同。请问这是NP完全问题吗？

小结：
贪婪算法寻找局部最优解，企图已这种方式获得全局最优解。
对于NP完全问题，还没有找到快速解决方案。
面临NP完全问题是，最佳的做法是使用近似算法。
贪婪算法易于实现、运行速度快，是不错的近似算法。

K最近邻算法：(挑选合适的特征，预测股票市场)
1.分类就是编组。
2.回归就是预测结果。

问题：

小结：
1.KNN用于分类和回归，需要考虑最近的邻居。
2.分类就是编组。
3.回归就是预测结果。
4.特征抽取意味着将物品装欢为一系列可比较的数字。
5.能否挑选合适的特征使馆KNN算法的成败。

跳表查询的时间复杂度分析

n/2、n/4、n/8、第k级索引节点的个数就是n/(2^k)

假设索引有h级，最高级的索引有2个节点。n/(2^h) = 2,从而求得h = log2(n) - 1

跳表:

原始链表大小为n，每2个结点抽1个，每层索引的节点数： n/2，n/4，n/8，…，8，4，2
原始链表大小为n，每3个结点抽1个，每层索引的节点数： n/3，n/9，n/27，…，9，3，1
空间复杂度是O(n)

跳表查询的时间复杂度分析
第k级索引
第k - 1 级索引

索引的高度：logn，每层索引遍历的节点个数：3
在跳表中查询任意数据的时间复杂度就是O(logn)

解决问题
升级维度
空间换时间

LRU最近最少使用
基于多链表来实现的。

可以通过HashMap + 双向链表实现。
HashMap保证通过key访问数据的时间为O(1)，
双向链表则按照访问时间的顺序一次穿过每个数据。
之所以选择双向链表而不是单链表，是为了可以从中间任意节点修改链表结构，而不必从头结点开始遍历。

1.二叉树遍历 前序、中序、后序 时间复杂度是多少？
O(n)，树的每个节点 有且仅访问一次。n为树的节点总数。

2.图的遍历时间复杂度是多少？
O(n)，n为图里面的节点总数。

3.搜索算法DFS、BFS时间复杂度是多少？
O(n) n指的是搜索空间里面的节点总数。

4.二分查找 时间复杂度是多少？
O(logn)

Q1：什么是 AVL 树？
AVL 树 是平衡二叉查找树，增加和删除节点后通过树形旋转重新达到平衡。右旋是以某个节点为中心，将它沉入当前右子节点的位置，而让当前的左子节点作为新树的根节点，也称为顺时针旋转。同理左旋是以某个节点为中心，将它沉入当前左子节点的位置，而让当前的右子节点作为新树的根节点，也称为逆时针旋转。

Q2：什么是红黑树？
红黑树 是 1972 年发明的，称为对称二叉 B 树，1978 年正式命名红黑树。主要特征是在每个节点上增加一个属性表示节点颜色，可以红色或黑色。红黑树和 AVL 树 类似，都是在进行插入和删除时通过旋转保持自身平衡，从而获得较高的查找性能。与 AVL 树 相比，红黑树不追求所有递归子树的高度差不超过 1，保证从根节点到叶尾的最长路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。

红黑树在本质上还是二叉查找树，它额外引入了 5 个约束条件：① 节点只能是红色或黑色。② 根节点必须是黑色。③ 所有 NIL 节点都是黑色的。④ 一条路径上不能出现相邻的两个红色节点。⑤ 在任何递归子树中，根节点到叶子节点的所有路径上包含相同数目的黑色节点。

这五个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果一个树的左子节点或右子节点不存在，则均认定为黑色。红黑树的任何旋转在 3 次之内均可完成。

Q3：AVL 树和红黑树的区别？
红黑树的平衡性不如 AVL 树，它维持的只是一种大致的平衡，不严格保证左右子树的高度差不超过 1。这导致节点数相同的情况下，红黑树的高度可能更高，也就是说平均查找次数会高于相同情况的 AVL 树。

在插入时，红黑树和 AVL 树都能在至多两次旋转内恢复平衡，在删除时由于红黑树只追求大致平衡，因此红黑树至多三次旋转可以恢复平衡，而 AVL 树最多需要 O(logn) 次。AVL 树在插入和删除时，将向上回溯确定是否需要旋转，这个回溯的时间成本最差为 O(logn)，而红黑树每次向上回溯的步长为 2，回溯成本低。因此面对频繁地插入与删除红黑树更加合适。

Q4：B 树和B+ 树的区别？
B 树中每个节点同时存储 key 和 data，而 B+ 树中只有叶子节点才存储 data，非叶子节点只存储 key。InnoDB 对 B+ 树进行了优化，在每个叶子节点上增加了一个指向相邻叶子节点的链表指针，形成了带有顺序指针的 B+ 树，提高区间访问的性能。

B+ 树的优点在于：

① 由于 B+ 树在非叶子节点上不含数据信息，因此在内存页中能够存放更多的 key，数据存放得更加紧密，具有更好的空间利用率，访问叶子节点上关联的数据也具有更好的缓存命中率。

② B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可。而 B 树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有 B+树好。但是 B 树也有优点，由于每个节点都包含 key 和 value，因此经常访问的元素可能离根节点更近，访问也更迅速。

Q5：排序有哪些分类？
排序可以分为内部排序和外部排序，在内存中进行的称为内部排序，当数据量很大时无法全部拷贝到内存需要使用外存，称为外部排序。

内部排序包括比较排序和非比较排序，比较排序包括插入/选择/交换/归并排序，非比较排序包括计数/基数/桶排序。

插入排序包括直接插入/希尔排序，选择排序包括直接选择/堆排序，交换排序包括冒泡/快速排序。

Q6：直接插入排序的原理？
稳定，平均/最差时间复杂度 O(n²)，元素基本有序时最好时间复杂度 O(n)，空间复杂度 O(1)。

每一趟将一个待排序记录按其关键字的大小插入到已排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

1.从1加到n的和的公式
S=n(n+1)/2。
因为S=1+2+3+…+n，并且，S=n+(n-1)+(n-2)+…+1，把这两个等式左右分别相加可以得到：2S=(n+1)+(n+1)+(n+1)+…+(n+1)，其中等式右边一共是
n个（n+1)相加是很容易数出来的，所以得到 2S=n(n+1)，于是S=n(n+1)/2。

2.等差数列和公式：Sn=n(a1+an)/2=na1+n(n-1)/2 d

3.等比数列求和公式：当q≠1时 ，Sn=a1(1-q^n)/(1-q)=(a1-anq)/(1-q)
当q=1时Sn=na1
(a1为首项，an为第n项，d为公差，q 为等比)

4.等差数列 前n项和公式为：
Sn=na1+n(n-1)d/2或Sn=n(a1+an)/2(2)
从等差数列的定义、通项公式，前n项和公式还可推出：
a1+an=a2+an-1=a3+an-2=…=ak+an-k+1，k∈{1,2,…,n}
若m，n，p，q∈N*，且m+n=p+q，则有
am+an=ap+aq
Sm-1=(2n-1)an，S2n+1=(2n+1)an+1
Sk，S2k-Sk，S3k-S2k，…，Snk-S(n-1)k…或等差数列，等等。

5.Fib
0,1,1,2,3,5,8,13,21,…
F(n) = F(n-1) + F(n-2);

6. 二分查找 时间复杂度O(logn) 公式 T(n) = T(n/2) + O(1)
   二叉树遍历 时间复杂度O(n) 公式 T(n) = 2T(n/2) + O(1)
   排好序的二维矩阵二分查找 时间复杂度O(n) 公式 T(n) = 2T(n/2) + O(logn)
   归并排序 时间复杂度O(nlogn) 公式 T(n) = 2T(n/2) + O(n)

数据结构题目一直是面试官考察的重点。数组和字符串是两种最基本的数据结构。链表应该是面试题中使用频率最高的一种数据结构。如果面试官想加大面试难度，那么
他很有可能会选用与树(尤其是二叉树)想关的面试题。由于栈与递归调用密切相关，队列在图(包括树)的宽度优先遍历中需要用到，需账务这两种数据结构。

算法是面试官喜欢考察的另外一个重点。
查找(特别是二分查找)和排序(特别是快速排序和归并排序)是面试中经常考察的算法，应聘者一定要熟练掌握。
回溯法很适合解决迷宫及其类似的问题。如果面试题是求一哥问题的最优解，那么可以尝试使用动态规划。假如我们在用动态规划分析问题时发现每一步都存在一个能
得到最优解的选择，那么可以尝试使用贪婪算法。另外，应聘者还要掌握分析时间复杂度的方法，理解即使同一思路，基于循环和递归的不同实现，他们的时间复杂度
可能大不相同。很多时候我们会用自上而下的递归思路分析问题，却会基于自下而上的循环实现代码。
位运算是针对二进制数字的运算规则。需掌握二进制的与、或、异或运算及左移、右移操作，就能解决与运算相关的面试题。

不使用新的变量，交换两个变量的值。比如有两个变量a、b，我们希望交换他们的值。有两种不同的方法：
基于加减法：
a = a + b
b = a - b
a = a - b
基于异或运算：
a = a ^ b
b = a ^ b
a = a ^ b

位运算是把数字用二进制表示之后，对每一位上0或者1的运算。
与(&) 0 & 0 = 0 1 & 0 = 0 0 & 1 = 0 1 & 1 = 1
或(|) 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1
异或(^) 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1 ^ 1 = 0

把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的1变为0。
很多二进制问题都可以用这种思路解决。