适用前提

1、简言之：可以找到一个局部最优解；可以从局部最优解推广到全局最优解
2、严谨地说，两个条件分别是最优子结构和贪心选择性质
3、一般来说，贪心法往往是将某个东西排序，或者用堆(优先队列)等数据结构，每一步都取局部最优解，进而得到全局最优解

邻接表

1、在计算机中，图的存储方式有多种，最常用的是邻接表和邻接矩阵。邻接矩阵由于适用范围很小，故一般不考虑这种写法
2、出度：如下图便是一幅有向图，其中一个节点指向的其他节点称为这个节点的出度，指向出度节点的路径称为这个节点的出边。如下图中 2、5 为 1 的出度
3、邻接表：就是将一个点的所有出点(邻接点)保存在一个数组中；拓展的过程，也就是遍历这个数组的过程。这个数组我们称为邻接表

素数判断

1、最简单的判断质数的方式，便是从 2~x 依次尝试，如果尝试到有因子，则其不是质数。需要特判 2 为质数、小于 2 的都不是质数(质数范围是大于 1 的自然数)
2、朴素筛法可以简单进行优化，实际需要尝试的因子最多只到sqrt(x)。比如判断 25 时，易知只需要判断 2~5 有没有因子，因此不需要重复判断大于sqrt(x)的因子。提前使用变量记录sqrt(x)，可以避免循环中重复计算sqrt的开销
3、但假如要计算 2 ~ 10⁶ 中有多少个质数时，只使用素数判断的效率很低(10⁶ - 218ms)，其额外判断了大量无用的数据，所以需要效率更高的筛法

二叉查找树

1、二叉查找树：又称二叉排序树/二叉搜索树，其任意节点与其左右子节点的大小关系都有左 < 中 < 右，其中序遍历会得到一个递增序列，常用于元素的排序和查找，如下图
2、查找元素：二叉查找树是以二分查找为原型的数据结构，因此其查找操作的时间复杂度为 O(log₂n)。其查找元素的动作为从根节点起，如果要查找的值比根小，则继续查找左子树，否则查找右子树
3、插入元素：与查找元素类似。如在下面的二叉查找树中插入新元素 12，应放在元素 11的右子节点处(从根节点依次比较 12 与 10、13、11 的关系)
4、删除元素：实质是保持中序遍历(即递增序列)的顺序不变从中删除节点，重点在于如何填补空缺。如下图展示了三棵二叉树，分别代表三种删除情景：情景一要删除节点 6(只有一边子树)，可以直接将子树整体上移；情景二要删除节点 7(两边都有子树)，可以将其中序遍历的前/后一个节点(即节点 6 或 8)填充到此处；情景三要删除节点 10，如果选择填充节点 14(其仍有子树)，则还应递归处理 14 的空缺(按照前两种情景选择方法处理)

认识树结构

1、树：指有层次关系的N 个节点的有限集合(如下图)；对于空树，N = 0；对于非空树，有且仅有一个根。除根外，可分为多个互不相交的有限集合，称为子树
2、节点：每个数据就是一个节点。节点可分为分为根节点、分支节点、叶子结点。在两个节点的关系上分为前驱(父节点)和后继(子节点)
3、在树中：边用来表明两个节点之间的层次关系(父子关系)；高度指的是深度(层次)，树的高度指的是整个树最深的层次数，如下图E 的高度为 3，树的高度为 4；度指的是边的个数(子节点的个数)，树的度指的是整个树各节点度的最大值，如下图A 的度为 3，C 的度为 1，树的度为 3

引入

1、对于模意义下的运算，例如我们知道有(a + b) % p = (a % p) + (b % p)或者(a * b) % p = (a % p) * (b % p)成立，但是对于模意义下的除法却不成立：(a / b) % p != (a % p) / (b % p)。不过，我们可以把模意义的除法转换成模意义的乘法
2、举例探讨：(7 / 2) % 5 中，把除法转成乘法写作 (7 * (1/2)) % 5，再将分数写成幂的形式写作 (7 * 2^-1) % 5
3、由于取模运算的结果一定是整数，所以 (7 * 2^-1) % 5 结果一定是整数，即说明必定能把 2^-1 这个分数转换成某个整数。所以，问题的关键就在于能转换成哪个整数
4、这时便需要引入乘法逆元的概念了，它可以辅助我们完成模意义的除法到模意义的乘法的转换

欧几里得算法

1、求两个数的最大公约数，除了分解质因数法，我们通常使用欧几里得算法(即辗转相除法)，其思路如下
2、求m,n 的最大公约数，就计算 m / n，然后令m = n、n = m % n，继续循环计算。直到n = 0时停止，这时的m就是最大公约数；或者提前一步，到m % n == 0(结果余数为 0)时停止，这时的n就是最大公约数(推荐后者，在写拓展欧几里得算法时更方便)
3、gcd 的性质：gcd(a, b) = gcd(a, k*a+b)；gcd(k*a, k*b) = k * gcd(a, b)；a / gcd(a, b)与b / gcd(a, b)互素；多个整数的最大公约数gcd(a, b, c) = gcd(gcd(a, b), c)；a 大于 b 时，gcd(a, b) = gcd(a, b-a)

引入

1、假设我们要计算 aⁿ 的值，最朴素的做法是循环 n 次，每次在结果上乘以 a。显然这种做法的时间复杂度为 O(n)，但当n 非常大时这种做法的效率仍然较低，而快速幂可以解决这个问题
2、我们先从一个特例引入：当n 是 2 的幂时，例如求 a⁶⁴ 的值，我们可以按照下表的方式计算。每次将上一次循环得到的结果自乘，就得到了指数为下一级 2 的幂的结果，以此类推，便很快就能得到指数为所求 2 的幂的结果
3、而对于任意的 n，例如求 a¹⁰⁵ 的值，我们可以将指数 n 拆分成多个 2 的幂之和，例如 a¹⁰⁵ = a^{1 + 8 + 32 + 64} = a¹ * a⁸ * a³² * a⁶⁴，而单独计算这些幂便十分简单了，因此最终只需要将需要的 2 的幂的结果相乘即可
4、因此，快速幂又称二进制取幂(平方法)，其英文为Binary Exponentiation，其时间复杂度仅需 O(log n) 对数级