AVL 的自平衡机制： 1、左旋转 2、右旋转 在什么时候维护平衡？ 加入节点后，沿着节点向上维护平衡性。 时间复杂度 O(logn) AVL 优化：在维护每一个节点之前，都需要对 AVL 的高度进行重新的计算， 但是如果我们重新计算出的这个节点的高度与原先的高度

1、实现基本功能：增删改查、各种判断方法等等 2、使用 泛型 让我们的数据结构可以放置 "任何"（不可以是基本 数据类型，只能是类对象，好在每一个基本类型都有一个对应的 包装类，它们之间可以自动进行装箱和拆箱的操作） 的数据类型 3、数组的扩容与缩容 手写时的易错点： 1、注意数

数组最大的优点：快速查询 数组最好应用于"索引有语义"的情况（但并非所有有语义的索引都适用于数组，例如身份证号码） 我们需要额外处理索引有语义的情况 数组的容量：capacity，数组的大小：size，初始为0 1、实现基本功能：增删改查、各种判断方法等等 2、使用 泛型 让我们的数据结构可以放置

数组队列实现： 其中 enqueue 的时间复杂度为 O（n)，需要使用循环队列改进为 O（1）。 @param <E>

栈的一种实现方式：使用动态数组实现栈 @param <E> 栈中的元素

树结构本身是一种天然的的组织结构，用树存储数据能更加高效地搜索。 二叉树：和链表一样，动态数据结构。 1）、对于每一个节点，最多能分成2个节点，即左孩子和右孩子。 2）、没有孩子的节点称为叶子节点。 3）、每一个孩子节点最多只能有一个父亲节点。 4）、二叉树具有天然的递归结构，即每个节点的左右子树

映射 Map 1）、存储 Key：value 数据对的数据结构。 2）、根据 Key，寻找 Value。 非常容易使用链表或者二分搜索树来实现。 LinkedListMap BSTMap 平均 最差 add、r

二分搜索：[0, n-1] 区间搜索版

对于有序数列，才能使用二分查找法（排序的作用）。 100 万的数据量只需零点几秒。 注意搜索开闭区间的设定，例如 [0, n - 1] 或 [0, n)。 1962 才意识到的 bug：mid = (l + r) / 2 可能会产生整形溢出，推荐使用减法：l + (r-l)/2。 如何写出正确的程

从左到右不断交换相邻逆序的元素，在一轮循环之后，可以让未排序的最大元素上浮到右侧。 优化：在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

大顶堆实现堆排序： 1、构建初始堆，将待排序列构成一个大顶堆：序列对应一个完全二叉树；从最后一个分支结点（n/2）开始， 到根（1）为止，依次对每个分支结点进行下沉，以便形成以每个分支结点为根的堆，当最后对树根结点进行 调整后，整个树就变成了一个堆。 2、将堆顶元素与堆尾元素交换，并从待排序列中移除

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。 对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素， 令逆序数量减少 1，因

为什么链表很重要？ 不同于 动态数组、栈、队列的实现：其底层是依托静态数组，靠 resize 解决固定容量问题， 链表是真正的动态数据结构，也是最简单的动态数据结构。 能够帮助我们更深入地理解引用（指针）与递归。 优势：真正的动态，不需要处理固定容量的问题。

BST 和 LinkedList 都属于动态数据结构 BSTSet 和 LinkedListSet 时间复杂度对比（h 为二分搜索树的高度） LinkedListSet BSTSet 最优 平均 最差（二分搜索树退化为线性链表时）

Definition for singly-linked list.

循环队列： 采用队尾和队首两个指针：front、tail，目的是将普通队列中的 出队 时间复杂度降为 O（1），省去复制数组的操作。 @param <E>

数据结构地图： 1、线性结构：动态数组、普通队列、栈、链表、哈希表。 2、树形结构：二分搜索树、AVL 树、红黑树 堆、线段树 多叉树：Trie、并查集 3、图结构：邻接表（与链地址法的哈希表很像，它是一个有

并查集：由孩子指向父亲，通常用来解决连接问题，最适合合并与查询是相互交替动态进行的请求。 应用场景： 1、网络中节点间的连接状态，网络是一个抽象的概念，用户之间也可以形成网络。 2、数学中的集合类实现，求集合中的并集。 连接问题和路径问题 类比为 堆和顺序表，我们只需要判断它是不是连接的或是最大

两类查找问题： 1、查找有无：元素 a 是否存在？set；集合。 2、查找对应关系（键值对应）：元素 a 出现了几次？map；字典。 常见操作： 1、insert 2、find 3、erase 4、change（map） JsonChao

栈的应用： 1）、无处不在的撤销操作 2）、系统栈的调用（操作系统） 3）、括号匹配（编译器）

普通队列：先进先出，后进后出 优先队列：出队顺序和入队顺序无关，和优先级相关 应用场景：操作系统的任务调度，动态 选择优先级最高的任务进行处理。医生和患者之间的关系。 优先队列底层实现 入队 出队 普通线性结构 O(1) O(n) 顺序线

栈问题 JsonChao的栈核心题库：8题

什么是哈希函数？ 哈希函数：将 "键" 转换为 "索引"，每一个 "键" 对应唯一的一个索引。 很难保证每一个 "键" 通过哈希函数的转换对应不同的 "索引"，因此会产生哈希冲突。 "键" 通过哈希函数得到的 "索引" 分布越均匀越好。 在哈希表（空间换时间）上操作，主要要考虑如何解决哈希冲突

什么是动态规划？ 斐波那契数列——解决递归中的 重叠子问题 && 最优子结构：通过求子问题的最优解，可以获得原问题的最优解： 1、记忆化搜索避免重复运算，自上而下的解决问题。 2、动态规划，自下而上的解决问题。 动态规划将是将原问题拆解成若干个

队列的基本应用 - 广度优先遍历 JsonChao的队列核心题库：9题

Bloom Filter 布隆过滤器： 1、一个很长的二进制向量和一个映射函数。 2、用于检索一个元素是否在一个集合中。 3、优点是空间和查询时间效率越超一般算法，缺点是有一定的误识别率（仅当存在时）和删除困难， 所以仅仅是一个预先处理模块。 位运算操作：

贪心算法: 它也存在最小生成树与最短路径中。 JsonChao的贪心算法题库：3题

二叉树天然的递归结构，空也是一颗二叉树。 JsonChao的二叉树核心题库：20题

递归：本质就是将原来的问题转换为更小的问题。 1）、注意递归函数的宏观语义。 2）、递归函数就是一个普通的函数，仅完成一个功能而已。 递归算法通常分为两步： 1）、求解基本问题。 2）、把原问题转化为更小的问题。 递归调用是有代价的：函数调用 + 系统栈空间 其它常见的链表类型： 1）、双

Trie:字典树，前缀树，多叉树 作用：专门为处理字符串而设计的 字典与 Trie 的比较： 字典：如果有 n 个条目，使用平衡二叉树查询的复杂度为 O（logn），100万(2^20)的数据量其 logn 大概为 20。 Trie：查询的时间复杂度为 O（w），w 为查询单词的的长度，大多数

链表，在节点间穿针引线 JsonChao的链表核心题库：22题

什么是算法面试？ 1、不代表能够"正确"回答每一个算法问题，但是合理的思考方向其实更重要， 也是正确完成算法面试的前提。 2、算法面试优秀并不意味着技术面试优秀，而技术面试优秀也并不意味着能够拿到 Offer。 3、把面试的过程看作是和面试官一起探讨一个问题的

向堆中添加元素（上浮，Sift Up） O（logn） 从堆中取出最大元素（下沉，Sift Down） O（logn） replace：取出最大元素后，放入一个新元素。 实现1：可以先 extractMax，再 add，两次 O（logn）操作。 实现2：可以直接将堆顶元素替换以后 Sift Do

思路：归并排序的思想是不断地将数组分成两部分，分别进行排序，然后归并起来， 归并就是将数组中两个已排序的部分归并成一个。归并排序是稳定性算法。 时间复杂度：O(NlogN) 空间复杂度：O(N)

Node 应该被设置成私有的，用户对此是无感知的。

Node 应该被设置成私有的，用户对此是无感知的。

用最大堆实现的优先队列 在 100 万个元素中选取前 100 个元素？ 使用优先队列，维护当前看到的前 100 个元素，需要使用最小堆，也可以使用最大堆（将常规的优先级定义取反即可） 使用 TreeMap 求频次 @param <E>

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。 可以利用这个特性找出数组的第 k 个元素。该算法是线性级别的，假设每次 能将数组二分，那么比较的总次数为

归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序； 快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素， 右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。 快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。 快速排序最好的情

算法导论中给出的5条红黑树的定义太生硬，并不能让人理解到底什么才是红黑树。 而算法4的作者 Robert Sedgewick 是红黑树的发明人之一，而他正是现代计算机科学之父 Donald Knuth 的弟子，可以挑战下 Donald Knuth 的两大著作：《计算机编程的艺术》 红黑树与2-3树