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

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

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

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

队列 队列（Queue）是一个数据集合，仅允许在列表的一端插入，在另一端删除。进行插入的一端称为“队尾”（rear），插入的动作称为入队；进行删除的一端称为“队头”（front），删除的动作称为出队。队列的性质是先进先出（FIFO，First-in-First-out）。下图为一个例子： 队列的实现方式：环形队列 设队列的最大长度为maxsize，…

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

广度优先搜索 广度优先搜索（BFS，Breadth First Search） 的一个常见应用是找出从根结点到目标结点的最短路径，其实现用到了队列。下面用一个例子来说明BFS的原理，在下图中，我们BFS 来找出根结点 A 和目标结点 G 之间的最短路径。 首先初始化一个队列Q，将根节点入队：A A出队，将与A相邻的节点入队，此时队列为BCD B出队…

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

平衡二叉树 什么是平衡二叉树： 每个节点的两个子树的高度不会相差超过1。普通树和平衡二叉树的对比： 为什么要用到平衡二叉树： 在二叉搜索树里面，搜索操作的时间复杂度从$O(logN)$到$O(N)$不等，这是一个巨大的性能差异。而平衡的二叉搜索树的搜索复杂度为$O(logN)$。 常见的平衡二叉树的实现： 红黑树、AVL树、伸展树、树堆 判断是否为…

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