Pat-Algorithm

2019-11-23 - 2020-1-1

PAT甲/乙级一刷

1. 基本的数学运算

   这部分问题需要注意常见的一些边界条件，二刷时需要放轻权重

2. 线性数据结构

   主要这里指的是链表，涉及到链表中数据关系的转换，通常有反转。常见的边界条件有某个节点不在链表中。

3. 栈和队列

4. 贪心

   涉及到贪心问题难度不一,首先需要明确问题使用贪心可解(归纳法证明)。才可以使用贪心策略解决问题。

5. 搜索

6. 树

   涉及到树的遍历，通常情况下比较简单。
   另一类问题主要涉及到并查集的问题，需要结合题目数数据规模，考虑并查集是否需要路径压缩.

7. 二叉树

   涉及到二叉树的遍历，通过任意两个遍历方式去还原二叉树原本的结构是常用题型。
   	注意到，给出序列不包含中序遍历序列时，遍历的结果可能不止有一个。

8. 图的遍历

   图的问题需要注意使用深度优先搜索遍历时，对访问过的元素需要作出标记。否则不会到达递归边界。

9. 图最短路径问题

   涉及到Dijkstra算法的使用,主要是由路径长度外第二个参数作为指标，需要记录已经计算出来的最短路径。并通过计算这些路径的第二参数指标，完成最后所求解。

10. 图连通性的问题

    图的连通性问题主要通过三种方式解决
    	1. 基本的图遍历,通过遍历给定序列的所有节点，计算连通图的数量
    	2. prim法则: 以顶点为扩充条件的连通图计算方法
    	3. kruskal法: 以边为扩充条件的连通图计算方法

11. 简单的动态规划问题

    1. 最大连续不下降子列问题

12. 排序问题

    这里的排序通常是指的是多关键字排序，注意参加排序的数据范围，以及排序方式

13. 分块查找

14. 树状数组

    某些题目，如果不使用树状数组，无论如何去优化时间复杂度都会导致TLE。

下一阶段需要注意的问题 (1-8 - 1-25)

1. 图问题的处理
2. 动态规划的处理
3. 深入学习树相关的高级数据结构
	AVL,红黑树，Trie树，B+/-树
4. 深入学习图的DAG的处理方案
5. 完成数据结构原理部分的补全工作