- 通过行数和列数的规律，进行输出
- 定义一个二维数组，通过规律填充，然后输出二维数组
- eg: 3_B1036.cpp
- 思路: 小日期不断增加，直到等于大日期
- 定义一个二维数组
month[13][2]- 第一维表示 12 个月份
- 第二维为 0 表示平年天数，为 1 表示闰年天数
- 需要通过 10 进制中转
- 递归边界、递归式
- 用 hashTable[index] 记录当前 index 是否已经加入到排列中
- eg: 4_FullPermutation.cpp
- 考虑当前状态下的局部最优策略
- eg: 4_B1023.cpp
- 定理:
- b 为奇数，ab = a * ab-1
- b 为偶数，ab = ab/2 * ab/2
- eg: 4_FastPower.cpp
- 头、尾分别设置指针，然后向中间靠近，直到头指针 > 尾指针
- eg: 4_MergeSort.cpp
- eg: 4_QuickSort.cpp
- eg: 4_RandSelect.cpp
- 辗转相除法: gcd(a, b) = gcd(b, a % b)，递归实现
- for 循环的范围
[2 ~ sqrt(n)]
- Eratosthenes 筛法
- 筛选掉所有倍数
- 设置辅助数组，记录某个数是否被筛选
- eg: 5_Eratosthenes.cpp
- 定义静态链表的节点时，通常除了数据域和指针域外，还会设置一个节点性质的标记
struct Node { int data; int next; // 节点某一个性质，根据题目而不同 bool isInList; };
- 记得要初始化！
- 可能需要把有效节点全部移至数组左端
- eg: 7_A1032.cpp, 7_A1052.cpp
- 通过递归 (也就是栈) 可以很好地实现 DFS
- 注意 "死胡同" 和 "岔道口"，也就是递归的
边界条件和递归表达式 - "剪枝"，可以减少时间复杂度
- eg: 8_DFS.cpp
- 通过队列，while 循环迭代进行实现
void BFS(...) { queue<T> q; q.push(s); while (!q.empty()) { ... } }
- 要点
- 全局定义一些变量
- 定义结构体(类)
- 可能需要在结构体(类)中设置一些具有标记属性的性质
- 访问的条件判断
- eg: 8_BFS_1.cpp, 8_BFS_2.cpp
- 要么没有根节点，是空树
- 要么由根节点、左子树、右子树组成，且左右子树都是二叉树
- 二叉树节点的插入位置，就是 查找失败的位置
- 根据题目二叉树的性质，从左右子树中的一棵进行递归，最后到达空树的位置
- 必须得有中序遍历序列
- 中序遍历 + { 先序遍历 | 后序遍历 | 层序遍历 }
- 模板 (中序 + 先序)
- eg: 9_重建二叉树模板.cpp, 9_A1020.cpp
- eg: 9_A1053.cpp
- 该题注意点
- 普通树，用 vector 存子树的 index
- 最后按权值的大小输出，可以在读入某节点的子树下标后，对 vector 进行 sort，这样可以优先访问大权值
- 用 vector 保存 path 时，注意 push_back() 后别忘了 pop_back()
- 插入某个值，如果这个值查找失败，则查找失败的地方就是这个节点的插入位置
- eg: 9_BST模板.cpp
- 递归思想
- 对于某个节点N，用其前驱(后继)节点P去替换节点N，然后转化为去左子树(右子树)中去删除节点P，然后一直递归，直到递归到一个叶子节点，直接删除
- eg: 9_BST模板.cpp
- eg: 9_A1043.cpp
-
注意要理解 LL、LR、RR、RL 四种情况，搞清楚左旋、右旋
-
作题之前最好画个图
-
插入情况汇总 (P326)
树形 判定条件 调整方法 LL BF(root)=2, BF(root->lchild)=1 对 root 右旋 LR BF(root)=2, BF(root->lchild)=-1 对 root->lchild 左旋，再对 root 右旋 RR BF(root)=2, BF(root->rchild)=-1 对 root 左旋 RL BF(root)=2, BF(root->rchild)=1 对 root->rchild 右旋，在对 root 左旋
- 合并、查找、集合
- 合并两个集合、判断两个元素是否在同一个集合
- 迭代或者递归，寻找所属集合的根节点
- 使原本路径上的节点的父节点都是 集合的根节点
- eg: 9_UnionSet.cpp
- 大根堆、小根堆
- 完全二叉树
- 数组存储
- eg: 9_Heap模板.cpp
- 带权路径长度最小 (叶子节点的带权路径长度的和)
- 构建思想
- 反复选择权值最小的两个元素，不断合并，最后只剩下一个元素
- 想法是参照下面的模板，设置 priority_queue 的类型为
Node*，重写greater函数
- eg: 9_MinWeightPathLen.cpp
- 哈夫曼编码
- 针对一个确定的字符串
- 将字符串中每个字符出现的频率，作为节点的权值，构造哈夫曼树
- 二叉树左孩子为 0, 右孩子为 1,进行编码
- 邻接矩阵适合顶点数量较少情况
- 邻接表适合顶点数量较多情况
- 模板
// pseudo code void DFS(u) { visit[u] = true; for (u 的所有邻接点 v) { if (visit[v] == false) { DFS(v); } } } void DFSTraverse(G) { for (G 的所有连通图顶点 u) { if (visit[u] == false) { DFS(u); } } }
- eg: 10_A1034.cpp
- 模板
// pseudo code void BFS(u) { queue q; q.push(u); visit[u] = true; while (!q.empty()) { top = q.top();q.pop(); for (u 邻接顶点 v) { if (visit[v] == false) { q.push(v); visit[v] = true; } } } } void BFSTraverse(G) { for (G 的所有连通图顶点 u) { if (visit[u] == false) { BFS(u); } } }
- eg: 10_A1076.cpp
- 单源最短路径
- 当存在比当前的路径更短的路径时，进行更新
- pseudo code (P370)
- eg: 10_Dijkstra模板.cpp
- 解决最优化问题的算法
- 一个复杂问题分解成若干子问题，综合子问题的最优解
- 记录子问题的解，避免下次遇到相同的问题而导致重复计算
- 通过递归 (记忆化搜索) 或者迭代
- 必须拥有重叠子问题和最优子结构，才能使用动态规划求解
- 核心问题
- 设计 状态 和 状态转移方程
- 还有边界值
- 重叠子问题
- 被分成多个子问题，且子问题会重复出现
- 状态转移方程 (P427)
- 第 i 层的状态只与第 i+1 层的状态有关
- 最优子结构
- 一个问题的最优解由子问题的最优解有效地构造出来
- 如数塔问题中，每个 dp 都可以由 2 个子问题推导得到
- 分治: 子问题不重叠，不一定解决最优化问题
- 归并排序，快速排序
- 动态规划: 重叠子问题，一定是最优化问题
- 都必须有最优子结构
- 贪心: 没有被选择的子问题不会去求解，而是直接抛弃
- 动态规划: 总是考虑所有子问题结果，选取其中的最优
- 不需要枚举左端点，只需要右端点，记录以当前点为结尾的连续序列的最大和
dp[i] = max(dp[i], dp[i - 1] + A[i])- eg: 11_MaxConstantSqSum.cpp
- 同样不需要枚举左端点，只需要右端点，记录以当前点为结尾的不降序列的最大长度
dp[i] = {1 || dp[j] + 1}- eg: 11_LIS.cpp
- 不需要枚举左端点，记录当前点为结尾的最长公共子序列长度
dp[i][j] = {dp[i - 1][j - 1] + 1 || max(dp[i - 1][j], dp[i][j - 1])}- eg: 11_LCS.cpp
- 普通方法枚举端点，会出现有的无法状态转移的情况
- 按
字符串的长度和字符串的初始位置进行枚举 - eg: 11_Palindromic.cpp
- 考虑第 i 个物品的选择策略
dp[i][v] = max{dp[i - 1][v], dp[i - 1][v - w[i]] + c[i]}- 空间复杂度上可以进行优化
- 滚动数组 (一维数组)
dp[v] = max{dp[v], dp[v - w[i]] + c[i]}- 注意一维数组时，v 需要逆向枚举
- 如果正向枚举，
dp[i - 1][v - w[i]]会被覆盖 dp[v - w[i]]就会使用左边已经更新的值 (第 i 个)
- 如果正向枚举，
- eg: 11_01Bag.cpp
- 方法同 01 背包问题
dp[i][v] = max{dp[i - 1][v], dp[i][v - w[i]] + c[i]}dp[v] = max{dp[v], dp[v - w[i]] + c[i]}- 这时的一维数组 v 需要正向枚举
- 保证
dp[v - w[i]]是已经更新后的值 (第 i 个)
- 保证
- eg: 11_CompleteBag.cpp
next[i]是子串subStr[0...i]的最长相等前后缀的前缀最后一位的下标- 当
pattern[i] != pattern[j + 1]，j pointer 不断回溯j == nextArray[j] - 其实也就是 j pointer 回溯到上一个以相同字母开头的前缀的下标
- 代码与求解 next 数组几乎一致
- 可以将求 next 数组的过程看作是
pattern模式串自匹配 - eg: 11_KMP.cpp
- 回退的箭头就是 next 数组代表的位置
- 有序元素划分为若干块，分成
sqrt(N)(取上界)块，每块中有sqrt(N)(取下界)个元素 block[sqrt(N)]和table[N]数组block[sqrt(N)]用来记录每个块中有多少个元素table[N]用来记录每个元素的个数
- eg: 13_A1057.cpp