一、优先队列优先队列按照队列的方式正常入队，但按照优先级出队。有两种实现方式：堆（二插堆、多项式堆等等）和二叉搜索树。这里重点讲解二叉堆，关于二叉搜索树的内容见这篇文章。 堆是一种特殊的完全二叉树。大根堆： 完全二叉树的任一节点都比其孩子节点大。小根堆： 完全二叉树的任一节点都比其孩子节点小。堆的向下调整： 假设根节点的左右子树都是堆，但根节点不满足堆的性质，可以通过一次向下调整将其变成一个堆。因

一、并查集并查集（Union & find） 是一种树形的数据结构，用于处理一些不交集（Disjoint sets）的合并与查询的问题。初始化时把每个点所在集合初始化为其自身。Find： 确定元素属于哪一个子集，它可以被用来确定两个元素是否属于同一子集。Union： 将两个子集合并成同一个子集。 如下图所示，一开始有7个字母，每个都指向自己：根据某种规则，将相关的字母合并起来，即某个字母会

一、LRU缓存LRU（least recently used）最近最少使用缓存机制，在计算机的缓存满时，会最先淘汰近期最少使用的数据。示意图如下图所示：设缓存的大小为5，在缓存未满之前，ABCDEF依次进入缓存。当要缓存F时，A近期没有被使用，因此淘汰掉，F放到头的位置，剩下的往后挪。当再次进来C的时候，因为缓存里已经有C了，因此把C提到缓存的头来。再进来G的时候，G放到头，剩下的往后挪。 二、实

一、字典树字典树（Trie） 又称单词查找树或键树，是一种哈希树的变种。典型的应用是用于统计和排序大量的字符串（但不限于字符串），优点是可以可以最大限度地减少无畏的字符串比较，查询效率比哈希表高。Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询的时间。 比如有一个包含多个单词的列表：[‘word’, ‘work’, ‘code’, ‘coffe’]，可以下面的字典树表示： graph

一、二分查找使用二分查找的条件： 单调递增或递减 存在上下界 能够通过索引访问（数组更适合二分查找，链表不适合） 程序模板： left, right = 0, len(array) while left <= right: mid = left + (right - left) // 2 if array[mid] == target: return True elif arr

一、冒泡排序排序过程： 列表每两个相邻的数，如果前者大于后者，则交换这两个数；遍历列表，完成一趟排序 继续从头遍历，重复上述过程，直到没有发生交换为止def BubbleSort(a): if len(a) == 0: return None for i in range(len(a) - 1): exchange = False

一、动态规划1、从斐波那契数列说起斐波那契数列我们比较熟悉了，它的递推公式为$f(n)=f(n-1)+f(n-2)$，它的解法在《数据结构与算法——递归》这一节里也说过了。直接使用递归会造成很多重复计算，它的时间复杂度为$O(2^N)$；而使用记忆化，即将中间过程缓存起来，可以降到$O(N)$的时间复杂度。实际上这样的递归是“从上而下”的，我们可以“从下而上”地做，由$f(0)$和$f(1)$得到

一、位运算位运算： 直接对整数在内存中的二进制位进行操作。比如6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果。由于位运算直接在内存数据进行操作，不需要转为十进制，因此速度非常快。 常用的逻辑运算符：| 符号 | 描述 | 运算规则

一、哈希表1、哈希表的原理哈希表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。哈希表由直接寻址表和哈希函数构成。哈希函数$h(K)$将元素关键字$K$作为自变量，返回元素的存储下标。直接寻址表如下所示：$U$为键值的全域，包含了所有可能的键值，$K$为实际使用的键值，$T$为直接寻址表，每个关键字对应表中的一个位置，比如2、3、5、8这几个关键字对应了$T(2),T(3),T(5),

一、递归递归：在定义一个过程或函数时，出现本过程或本函数的成分称为递归。递归条件：可以用递归解决的问题应该满足以下三个条件： 这个问题可以转化为一个或多个子问题来求解，而且这些子问题的求解方法与原问题完全相同 递归调用的次数是有限的 必须有终止条件 递归的底层原理： 函数调用操作包括从一块代码到另一块代码之间的双向数据传递和执行控制转移，大多数CPU使用栈来支持函数调用。单个函数调用操作所使用