冒泡排序 排序过程： 列表每两个相邻的数，如果前者大于后者，则交换这两个数；遍历列表，完成一趟排序 继续从头遍历，重复上述过程，直到没有发生交换为止 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）满足的性质： 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。 一个二叉搜索树的例子如下所示： 因为二叉树的中序遍历会得到一个递增的序列，因此在二叉搜索树里中序遍历比较常用。 给定一个二叉树，我们要判断它是否是二叉搜索树。二叉搜索树的特征比较明显…

二叉树 二叉树是一种更为典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。下面是个二叉树的例子： 用python定义二叉树的节点： # 二叉树节点 class TreeNode: def __init__(self, x): self.val = x self.left = Non…