面试题汇总（数据结构）
数据结构和算法
链表
二叉树
二叉树的最大深度
考察二叉树的基本知识、递归思想。
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
解答：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
int left = maxDepth(root.left) + 1;
int right = maxDepth(root.right) + 1;
return left > right ? left : right;
}
}
二叉树的遍历
- 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
- 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
- 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
所谓的前中后是相对于当前节点而言。
二叉树的遍历
void preOrder(Node* root) {
if (root == null)
return;
print root // 此处为伪代码，表示打印root节点
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null)
return;
inOrder(root->left);
print root // 此处为伪代码，表示打印root节点
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null)
return;
postOrder(root->left);
postOrder(root->right);
print root // 此处为伪代码，表示打印root节点
}
Map
如何避免HashMap低效地扩容？
我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的 数据搬移到新散列表中。 当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过 程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。
如何设计一个支持LRU缓存淘汰算法的数据结构？
-
基于链表实现
思路是这样的：我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。 -
如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
-
如果此数据没有在缓存链表中，又可以分为两种情况：
如果此时缓存未满，则将此结点直接插入到链表的头部； 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
时间复杂度是 O(n)
2.基于跳表实现
加快查询速度
3.基于Map+双向链表实现（LinkedHashMap）
如果把LinkedHashMap中双向链表改成单链表，还能否正常工作呢？为什么呢？
在删除一个元素时，虽然能O(1)的找到目标结点，但是要删除该结点需要拿到前一个结点的指针，遍历到前一个结点复杂度会变为O(N），所以用双链表实现比较合适。
堆
堆是一种特殊的树。只要满足这两点，它就是一个堆。
- 堆是一个完全二叉树；
- 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标 为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样 就可以通过下标计算，把整棵树都串起来。
往堆中插入一个元素
堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。
我这里画了一张堆化的过程分解图。我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系。
image.png
删除对顶元素
我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满 足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。
因为我们移除的是数组中的最后一个元素，而在堆化的过程中，都是交换操作，不会出现数组中的 “ 空洞 ” ，所以这种方法堆化之后的结果，肯定满足完全二叉树 的特性。
堆的应用
- 优先队列
往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。
- 优先队列
- 2.高性能定时器
按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是 最先执行的任务。
这样，定时器就不需要每隔 1 秒就扫描一遍任务列表了。它拿队首任务的执行时间点，与当前时间点相减，得到一个时间间隔 T 。 这个时间间隔 T 就是，从当前时间开始，需要等待多久，才会有第一个任务需要被执行。这样，定时器就可以设定在 T 秒之后，再来执行任务。从当前时间点到 （ T-1 ）秒这段时间里，定时器都不需要做任何事情。
当 T 秒时间过去之后，定时器取优先级队列中队首的任务执行。然后再计算新的队首任务的执行时间点与当前时间点的差值，把这个值作为定时器执行下一个任务 需要等待的时间。 这样，定时器既不用间隔 1 秒就轮询一次，也不用遍历整个任务列表，性能也就提高了。 - 3.利用堆求Top K
如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比 较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完 之后，堆中的数据就是前 K 大数据了。 - 4.利用堆求中位数
我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。
如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；如果新加入的数据大于等于小顶堆的堆顶元素，我们就将这个新数据插入到 小顶堆。
合并有序小文件
假设我们有 100 个小文件，每个文件的大小是100MB，每个文件中存储的都是有序的字符串。我们希望将这100个小文件合并成一个有序的大文件。这里就会用到优先队列。
整体思路有点像归并排序中的合并函数。我们从这100个文件中，各取第一个字符串，放入优先队列中，然后比较大小，把最小的那个字符串放入合并后的大文件中，并从队列中删除。
假设，这个最小的字符串来自于 13.txt 这个小文件，我们就再从这个小文件取下一个字符串，并且放到优先队列中，重新比较大小，并且选择最小的放入合并后的大文 件，并且将它从优先队列中删除。依次类推，直到所有的文件中的数据都放入到大文件为止。
算法
如何快速判断某 URL 是否在 20 亿的网址 URL 集合中？
Java 数据结构和算法百大面试题
算法和编程面试题精选TOP50！(附代码+解题思路+答案)
Java HashMap 源码解析
Redis内部数据结构详解(6)——skiplist 2016-10-05
