0. 写在前面
这些问题是我备考数据结构和算法的过程中，详细总结的常见面试问题和答案。逐个搜索并记录下来，花了很大的精力！
1. 什么是数据？什么是数据结构？
数据是描述客观事物的符号，能够被计算机识别，并且给计算机处理的符号集合
数据结构是计算机内部组织数据的方式
2. 大O表示法
大O符号，又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个通常更简单的函数来描述一个函数数量级的渐近上界。
时间复杂度，是一个用于度量一个算法的运算时间的一个描述，本质是一个函数，它描述的只是代码执行时间随数据规模增长的变化趋势
3. 顺序表和链表
逻辑结构和物理结构，逻辑上都是相邻的元素，但是物理上，顺序表是相邻的，链表一般都是不相邻的
访问元素的时候，对于按值查找，都是O(n)，有序的话是O(log2n)
空间分配的情况，若顺序表是静态分配，空间固定，过多元素会溢出，若是动态分配，扩容存在时间消耗；链表的话则自由灵活
4. 链表反转
方式一：使用栈结构来反转，时间和空间开销不立理想
方式二：使用三指针来反转，效率高
5. 链表升序合并
方法一：递归，时间空间复杂度为O(n+m)
方法二：迭代，时间复杂度为O(n+m)，空间复杂度为O(1)
6. 栈和队列
队列是一端进行插入另一端进行删除的线性表
栈是表尾进行插入和删除的线性表
它们都可以用数组和链表来实现
7. 栈和队列的应用
前缀表达式和后缀表达式
8. 判断循环队列是否为空？
方法一：入队tag=1，出队tag=0
方法二：记录元素数量num
方法三：少用一个空间，（rear+1%maxsize=front
9. 各种二叉树的区别
完全二叉树和满二叉树：除了最后一层外，其他任何一层的节点数均达到最大值，且最后一层也只是在最右侧缺少节点
二叉排序树和二叉搜索树：都是一样的，节点值大于左子节点的数值，小于右边子节点的数值
平衡二叉树（AVL）：任意结点的左、右子树高度差的绝对值不超过1
10. 重建二叉树
根据前，中遍历次序构造二叉树和根据中，后序列构造二叉树，只需要找到头节点，然后递归找到左右子树就行了
至于为什么不能不能根据前，后序列构造出二叉树，是因为，我们只知道最开始头节点的位置，其余元素不清楚是划分到左子树还是右子树
重建二叉树的妙招https://www.bilibili.com/video/BV1Xu411d7qf
11. 二叉树的树深
递归：如果一棵树只有一个结点，它的深度为1。如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。如果既有右子树又有左子树呢？那该树的深度就是其左、右子树深度的较大值再加1
12. 二叉树的最近公共祖先
第一种情况：左子树和右子树均找没有p结点或者q结点；
第二种情况：左子树上能找到，但是右子树上找不到，此时就应当直接返回左子树的查找结果；
第三种情况：右子树上能找到，但是左子树上找不到，此时就应当直接返回右子树的查找结果；
第四种情况：左右子树上均能找到，说明此时的p结点和q结点分居root结点两侧，此时就应当直接返回root结点了。
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==p||root==q||!root)return root; TreeNode* left=lowestCommonAncestor(root->left, p, q); TreeNode* right=lowestCommonAncestor(root->right, p, q); if(!left&&!right)return NULL; else if(left&&!right)return left; else if(right&&!left)return right; return root; }
13. 二叉树的应用
二叉搜索树
任何节点的键值一定大于去其左子树中的每一个节点的键值，并小于其右子树的每一个节点的键值
二叉排序树（AVL）
在二叉搜索树的基础上，改善了树的结构。在二叉搜索树的插入和删除运算中，采用平衡树的优点是：因为树的结构较好，从而提高查找运算的速度。缺点是：是插入和删除运算变得复杂化，从而降低了他们的运算速度
哈夫曼树
哈夫曼树叶是子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树，是二叉搜索树的应用
应用：哈夫曼编码
14. 字典树的概率和应用
字典树用于统计，排序和保存大量的字符串，利用字符串的公共前缀来节约存储空间
应用：前缀匹配
15. 图的遍历
可以用邻接矩阵或邻接表来表示图
深搜和广搜的定义就不多讲了，它们的时间复杂度为
用邻接矩阵表示图：查找每个结点的邻接点的时间复杂度为O(n的平方），加上初始化visited数组时间复杂度O(n),DFS的时间复杂度为O(n的平方）
用邻接表表示图：查找每个结点的邻接点的时间复杂度为O（e),加上初始化visited数组时间复杂度O(n),DFS的时间复杂度为O(n+e)
16. 图的应用
最短路径：
Dijkstra时间复杂度O(n2) 适用于 权值为非负 的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)，空间
Floyd时间复杂度O(n3)，空间复杂度O(n)
最小生成树：
prim算法
Prim时间复杂度为O(n2)，适用于稠密图
prim算法的思想是，从一个起点开始，通过不断的纳入与当前生成树距离最短的且不在生成树中的点来构造最小生成树，当所有点都纳入到生成树以后，就得到了最小生成树。使用邻接表来存储图，能使得所需的空间最小。通过一个数组来存放各个点到当前生成树的最短距离，可以避免重复比较，从而提升效率。但我们所要获取的是该数组里的距离最小的那个点。如果没有进行堆优化，那从这个数组里找出最小距离的点的时间复杂度是O（n）,通过堆优化，我们获取最小值的时间复杂度则为O（log2n）,在图的点数目很大时，能有效的提升效率。
Kruskal：并查集的贪心算法，时间复杂度为O(ElogE)
拓扑排序
集合上的一个偏序得到该集合上的一个全序
关键路径
17. 查找算法
二分查找的原理和实现要知道！
B树和B+树
平衡多路查找树，即一个结点的查找路径不止左、右两个，而是有多个，最大孩子个数称为B树的阶。
B树特性：
节点内的关键字大小排列
树中每个结点至多有m 棵子树，即至多含有m-1 个关键字
若根结点不是终端结点，则至少有两棵子树
除根结点外的所有非叶结点至少有m//2 棵子树，即至少含有m//2- 1 个关键字
所有的叶结点都出现在同一层次上
B树好处：
B树的每一个结点都包含key(索引值) 和 value(对应数据)，因此方位离根结点近的元素会更快速。（相对于B+树）
B树的不足：
不利于范围查找(区间查找)，如果要找 0~100的索引值，那么B树需要多次从根结点开始逐个查找。
而B+树由于叶子结点都有链表，且链表是以从小到大的顺序排好序的，因此可以直接通过遍历链表实现范围查找。
散列表
只需要知道散列函数的特性
KMP
根据最大长度表next数组的值，在匹配失败后的，匹配字符串回溯到下一次匹配的具体位置
next数组标记的是，匹配字符串当前索引及其之前的子串最大长度相同前缀和后缀的数量
18. 排序算法
快排原理和实现要知道！
快速排序和归并排序
归并排序和快排的相同点：
1，利用分治思想
2，具体实现都用递归
归并排序和快排的不同点：
时间复杂度
快速排序期望的复杂度是O(nlogn)，最差情况为O(n2)；归并排序的最差最好情况均为O(nlogn)。归并排序的稳定性要比快速排序高 , 二者时间复杂度相当 ;
空间复杂度
从空间复杂度来讲 , 归并排序 的空间复杂度是 O ( n ) , 快速排序 的空间复杂度是 O ( 1 ) O(1)O(1) , 快速排序没有使用额外的空间 , 在数组原地进行排序 ,
排序稳定性
快排不稳定，归并稳定
局部和整体有序
快速排序是先整体有序 , 然后局部有序
归并排序 是 先局部有序 , 然后整体有序 (归并排序 先根据中心点分成两部分 , 左侧和右侧分别进行排序 , 两遍都排序完毕后 , 再组合到一起 )
桶排序
属于计数排序的一种
19. 贪心，动态规划，分治
贪心就利用局部的最优解来得到一个整体的结果，它不能保证整体最优。它的结果与选择的贪心策略有关
分治是将原问题分解为n个规模小，和原问题类似的子问题，通过子问题的解合并为原问题的解
动态规划也是一种分支，它可以利用前面的子问题的解来得到后面的子问题解，可以有效避免求重复的子问题。
在求解的过程中，保留可能得到的局部最优解，去掉其他局部解，解决到当前的局部最优解。最终得到全局最优的解。
20. 哈希
哈希表
哈希表是一个典型的用空间换时间的操作，利用数组随机访问的特性，最大化查找效率的数据结构。哈希过程就是将数组元素与下标建立关系的过程。
哈希表冲突怎么解决
开放定址法
线性探测
平方探测
再散列
散列表
21. 求数组最大子序列和
①如果前面的累加值为负数或者等于0，那对累加值清0重新累加，把当前的第i个数的值赋给累加值。
②如果前面的累加值为整数，那么继续累加，即之前的累加值加上当前第i个数的值作为新的累加值。
22. 快排算法
T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间
时间复杂度：最差为O（n^2），每次都取到最大或者最小，退化为冒泡排序，最优为O（nlogn），每次都取到中间，平均为O（nlogn）
空间复杂度：快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据，最差为O（n），退化为冒泡排序，最优为O（logn）
public class QuickSort { public static void sort(int a[], int low, int hight) { int i, j, index; if (low > hight) { return; } i = low; j = hight; index = a[i]; // 用子表的第一个记录做基准 while (i < j) { // 从表的两端交替向中间扫描 while (i < j && a[j] >= index) j--; if (i < j) a[i++] = a[j];// 用比基准小的记录替换低位记录 while (i < j && a[i] < index) i++; if (i < j) // 用比基准大的记录替换高位记录 a[j--] = a[i]; }/ a[i] = index;// 将基准数值替换回 a[i] sort(a, low, i - 1); // 对低子表进行递归排序 sort(a, i + 1, hight); // 对高子表进行递归排序 } public static void quickSort(int a[]) { sort(a, 0, a.length - 1); } public static void main(String[] args) { int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 }; quickSort(a); System.out.println(Arrays.toString(a)); } }
23. 归并排序
时间复杂度：比较稳定O（nlogn），因为无论哪种情况，做的操作都差不多
空间复杂度：归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)
更稳定，空间耗费更大
import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] arr = {11,44,23,67,88,65,34,48,9,12}; int[] tmp = new int[arr.length]; //新建一个临时数组存放 mergeSort(arr,0,arr.length-1,tmp); System.out.println(Arrays.toString(arr)); } public static void merge(int[] arr,int low,int mid,int high,int[] temp){ int i=0; int j=low,k=mid+1; while(j<=mid&&k<=high){ if(arr[j]<=arr[k]){ temp[i++]=arr[j++]; }else{ temp[i++]=arr[k++]; } } while(j<=mid){ temp[i++]=arr[j++]; } while(k<=high){ temp[i++]=arr[k++]; } for(int t=0;t<i;t++){ arr[low+t]=temp[t]; } } public static void mergeSort(int[] arr,int low,int high,int[] temp){ if(low<high){ int mid=(low+high)/2; mergeSort(arr, low, mid, temp); mergeSort(arr, mid+1, high, temp); merge(arr,low,mid,high,temp); } } }
24. 如何用两个栈实现队列，如何用两个队列实现栈？
两个栈实现队列
假设初始两个栈为空
一个栈A用于维护add数据，另一个用于维护poll数据
当需要add的时候，直接添加到栈A的顶端即可；如果要poll，直接从栈B弹出数据，但是如果栈B为空，则需要将A中所有的对象，依次弹出存入B中，然后再进行poll
两个队列实现栈
假设初始两个队列为空，维护一个存入元素个数的变量n
当需要push元素的时候，直接加入到非空的队列（都为空就任加一个）；当需要pop元素的时候，将非空的队列依次取出前n-1个元素，存入另一个空队列，然后将第n个元素取出即可，如此反复
25. 循环引用怎么解决
循环引用指两个对象相互强引用了对方，从而导致两个对象都无法被释放，引发了内存泄漏现象，互相引用变量的引用计数都为1，本质上是引用计数的原因。
只靠强引用计数方式，会存在循环引用的问题，导致对象永远无法被释放，弱引用就是专门用来解决循环引用问题的：
「若 A 强引用了 B，那 B 引用 A 时就需使用弱引用，当判断是否为无用对象时仅考虑强引用计数是否为 0，不关心弱引用计数的数量」
这样就解决了循环引用导致对象无法释放的问题，但这会引发野指针问题：当 B 要通过弱指针访问 A 时，A 可能已经被销毁了，那指向 A 的这个弱指针就变成野指针了。在这种情况下，就表示 A 确实已经不存在了，需要进行重新创建等其他操作
26. 什么是拓扑排序
在图论中，拓扑排序（Topological Sorting）是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：
每个顶点出现且只出现一次
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面
