二分查找 使用二分查找的条件： 单调递增或递减 存在上下界 能够通过索引访问（数组更适合二分查找，链表不适合） 程序模板： 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…

位运算 位运算： 直接对整数在内存中的二进制位进行操作。比如6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果。由于位运算直接在内存数据进行操作，不需要转为十进制，因此速度非常快。 符号 描述 运算规则 & 与 两个都为1时，结果才为1 | 或 两个都为 0时，结果才为1 ^ 异…

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

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

渐进记号 五种渐进记号 大$O$记号： 对于给定函数$g(n)$，$f(n)=O(g(n))$：存在正常量 $c$ 和 $n_{0}$，使得对所有 $n \geq n_{0}$，有 $0 \leq f(n) \leq cg(n)$成立。$f(n)$ 只有一个渐进上界，$f(n)$ 的阶不高于 $g(n)$ 的阶。 $\Omega$记号： 对于给定函…

二叉搜索树 二叉搜索树（BST）满足的性质： 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。 一个二叉搜索树的例子如下所示： 因为二叉树的中序遍历会得到一个递增的序列，因此在二叉搜索树里中序遍历比较常用。 给定一个二叉树，我们要判断它是否是二叉搜索树。二叉搜索树的特征比较明显…