概述
经典算法：
- 二分查找
- 快速排序、归并排序
- KMP算法
- 快慢指针（双指针）
- 普利姆（Prim）、克鲁斯卡尔（Kruskal）算法
- 迪克斯特拉（Dijkstra）
- 优化算法：模拟退火、蚁群、遗传算法
复杂度
算法复杂度：大O表示法
空间复杂度：定义变量消耗空间，递归调用栈也需要计算
考虑最好情况、最坏情况、平均复杂度
分类
目的：搜索、排序、字符串、图、最优化、数学
方式：暴力、增量、分治、贪心、动态规划、回溯、分支限定
分治
大问题分小问题解决，再合并
递归可以很好的拆分合并
步骤：
- 拆分独立子问题
- 规模小时直接解，否则继续递归拆分
- 将子问题合并
场景：
- 二分搜索、大整数乘法、归并排序、快速排序
- 棋盘覆盖、循环赛日程表、汉诺塔
贪心
总是做出当前最好的，做到局部最优，不考虑整体最优
场景：
- 哈夫曼编码（根据字符出现的频率，用0/1表示）
- 直接求解全局最优（需要无后效性）
动态规划
过程：
- 原问题分成多个阶段，依次决策，得到局部解
- 每次决策依赖当前状态、才发生状态转移
场景：
- 最优二叉树搜索树、最长公共子序列、背包问题
回溯
- 一条路上发现不对就回到以前的步骤重新选择
- 通过解题
DFS深度优先搜索，树、图，其实就是回溯
分支限定
BFS广度优先搜索
每一层所有节点都记录，抛弃不符合条件的节点
每个节点作为下一个扩展节点继续搜索
数组问题
两数之和、三数之和（为零）、旋转图像（22/8/11）
旋转图像中，
- 通过观察可得，矩阵转置再沿着中间对称即可得到旋转后的图像
- 分治法中，将图像划分四个区域（除去不需要移动的），观察可得，(y,x)会移动到(n -x -1,y)，以此为规律，依次移动4个区域即可
