Pat-Algorithm

2019-11-23 - 2020-1-1

PAT甲/乙级一刷

基本的数学运算

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

线性数据结构

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

贪心

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

树

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

二叉树

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

图的遍历

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

图最短路径问题

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

图连通性的问题

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

排序问题

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

树状数组

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

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

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

sandexp / pat-algorithm Goto Github PK