贪心算法 Greedy Algorithm

1. 适用场景明确包含期望值和限制值
   • 一组数据中定义了限制值和期望值，求满足限制值的情况下，令期望值最大
2. 确定是否可以使用贪心算法
   • 每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大
3. 初步验证贪心算法求得的结果是否是最优
   • 尝试举几个例子
4. 不能使用贪心算法的问题的特征
   • 前面的选择，会影响后面的选择，例如 地图的最短路径

贪心算法的常见示例

1. 霍夫曼编码 Huffman Coding
   • 给字符进行编码，字符出现的频率越高，则编码后的符号越短
     • 任何字符的编码都不是另一个的前缀
     • 解压缩时，尽可能长地读取二进制串
   • 按照字符出现的频率，放入优先级队列中从小到大排列，若频率相同则按照出现次序排列
   • 构建霍夫曼树
     • 每次从队列中取出前两个元素（最小的两个元素），将它们的频率相加后，放入优先级队列中，仍旧保证优先级队列是有序的
   • 根据霍夫曼树进行编码
     • 给霍夫曼树中的所有左链接 0，右链接 1
     • 从根结点开始，依次记录所有字母的编码
2. Prim 最小生成树算法、Kruskal 最小生成树算法
3. Dijkstra 单源最短路径算法
4. 分糖果
   • 每次从剩下的孩子中找到需求最小的孩子
   • 从剩下的糖果中找到能满足他的最小的糖果
5. 钱币找零
   • 如果钱币的面额分布较为均匀，如 100、50、20，则可以使用贪心算法。每次找出最大面额的钱币支付
   • 如果钱币的面额分布不均匀，如 100、99、1，则贪心算法不再适用，需要使用动态规划 6.区间覆盖
   • n 个区间的最左端点为 lmin，最右端点为 rmax
   • n 个区间按照起始端点从小到大排序
   • 每次选择左端点和已经覆盖的区间不重合，右端点尽量小的

分治算法 Divide and Conquer

1. 原问题可以分解成一系列的子问题，且原问题与分解成的小问题有相同的模式
2. 原问题分解成的子问题可以独立求解，子问题之间没有相关性
3. 具有分解终止条件，在问题足够小时，可以直接求解
4. 可以将子问题合并成原问题，合并操作的复杂度不高

分治算法-递归操作

1. 分解，将原问题分解成一系列子问题
2. 解决，递归地求解各个子问题，若子问题足够小，则直接求解
3. 合并，将子问题的结果合并成原问题

分治算法的常见示例

1. 一组数据的有序对个数或者逆序对个数
   • 将数组分成前后两段 A1、A2，则数组的逆序对个数等于 A1 的逆序对个数 K1 与 A2 的逆序对个数 K2、A1 A2 的逆序对个数 K3 之和，即 K1 + K2 + K3
   • 借助归并排序，当 A1、A2 两个有序数组合并时，找出 A1 中比 A2 大的元素个数
   • 最后将结果全部相加，得到总的逆序对个数
2. 求平面内的最近点对
3. 矩阵计算

回溯算法 Backtracking Algorithm

枚举搜索的思想，有规律地枚举所有可能的解

回溯算法的常见示例

1. 八皇后
2. 0 - 1 背包
3. 正则表达式
4. 图的着色
5. 旅行商问题
6. 数独
7. 全排列

动态规划 Dynamic Programming

1. 适用场景
   • 用于求解最优问题，如最大值、最小值等
2. 思路
   • 把问题分解为多个阶段，每个阶段对应一个决策
   • 记录每个阶段可达的状态集合（去掉重复的）
   • 通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地向前推进

动态规划适用的问题

1. 动态规划适合解决的问题的模型（一个模型），即多阶段决策最优解模型
   1. 解决问题的过程中，需要经历多个决策阶段
   2. 每个决策阶段都对应着一组状态
   3. 求解最优解时，可以经过某组决策序列来找到
2. 三个特征
   • 最优子结构
     • 问题的最优解包含子问题的最优解，即可以通过子问题的最优解，推导出问题的最优解
     • 后面阶段的状态可以通过前面阶段的状态推导出来
   • 无后效性
     • 推到后面阶段的状态时，只需要关心前面阶段的状态值，而不需要关心这个状态值是怎么得到的
     • 某阶段的状态确定后，不受后面阶段的决策影响
   • 重复子问题
     • 不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态

动态规划解决思路

1. 状态转移表法
   • 先建立一个状态表（一般都是二维的，如果问题的状态比较复杂的话，可能是多维）
   • 状态表的每个状态包含三个变量，行、列、数组值
   • 根据决策的过程，从前往后递推地填充状态表
2. 状态转移方程法
   • 递归 + 缓存、迭代递推
   • 找到最优子结构
   • 推导出状态转移方程

动态规划 和 回溯算法 的关系

1. 根据回溯算法画出递归树
2. 如果存在子问题，则可以考虑是否能用动态规划实现
3. 如果不存在子问题，则回溯算法就是最优解

并行算法

并行处理的常见示例

1. 并行排序
   • 处理思想：先将数据进行分片，然后并行处理
   • 并行执行归并排序，先随意地对数据分片，排序之后再合并
   • 并行执行快速排序，先对数据按照大小划分区间，然后再排序，排完序后不需要合并
2. 并行查找
   • 使用散列表存储一定量的数据，当需要对散列表动态扩容时，会耗费很多不必要的内存
   • 将数据随机分割成 k 份，每份中的数据只有原来的 1/k，针对这 k 个小数据集合分别构建散列表
   • 当某个散列表的装载因子过大时，可以单独对这个小散列表进行扩容，这样不仅从内存的利用率或扩容的执行效率上，都比只使用一个大的散列表高效
3. 并行匹配字符串
   • 将一个大文本分割成 k 个小文本，并行地在这些小文本中查找关键词
   • 在相邻的两个小文本中，将前一个小文本的结尾取 m 个字符，后一个小文本的开始取 m 个字符，在这个 2m 的字符串中再查找一遍需要匹配的字符串
4. 并行搜索
   • 并行化广度优先搜索算法
   • 广度优先搜索是一种逐层搜索的搜索策略，可以基于当前结点，启动多个线程并行地搜索下一个层的顶点
   • 使用两个队列 A、B，多个线程并行地处理队列 A 中的顶点，并将扩展得到的顶点存储在队列 B 中。队列 A 中的顶点都遍历过之后，队列 A 被清空。再遍历队列 B 中的顶点，将扩展得到的顶点存储在队列 A 中。A、B 循环使用。