PAT甲级考前整理之一网址：https://www.cnblogs.com/jlyg/p/7525244.html，主要总结了前面131题的类型以及易错题及坑点。
PAT甲级考前整理三网址：https://www.cnblogs.com/jlyg/p/10364727.html主要是讲132题开始的题目。
考前注意：
1、写函数（有返回值的函数）容易忘记返回值，可能本地运行没问题，但是提交了就会有问题。
2、不要把strlen()函数写到for、while的循环中，有时候会超时，最好是 int len = strlen(str);提前求出来。
3、用sort比较的时候，比较函数 int comp(const ST& st1,const ST& st2);如果在comp中调用ST的fun函数，fun函数必须加上const,例子 int fun()const{return 0;}
4、二位数组初始化不要直接赋值，比如int a[10][10] ={0}，是错误的，应该使用memset(a,0,sizeof(a));（一维数组也最好不要直接复制，通过循环复制最好）
5、不要使用gets，PAT系统不支持。可以使用fprintf,使用fprintf注意最后一个字符是' ',特别是比较的时候就不相等了。使用这一类函数时，注意需要把前一个输入的' '使用getchar去掉。
string mygets() { char str[300]; fgets(str,sizeof(str),stdin); int len = strlen(str); if(str[len-1]==' ') str[len-1] = ' '; \最后一行可能没有换行符 return str; }
6、使用freopen("1.txt","r",stdin);来减少测试的时间。因为PAT里有定义ONLINE_JUDGE，所以你需要背一下，写错就没办了。用以下代码就无需在提交的时候修改就能提交（节约大量时间呀！！）
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; int main() { #ifndef ONLINE_JUDGE freopen("test.txt","r",stdin); #endif // ONLINE_JUDGE return 0; }
7、输出时注意单复数，比如单数是a、is，复数是加s、are。
8、不要还没输入完就用break跳出，不然会有问题，具体可以看我以下代码和代码中的注释，例题PAT1122
View Code9、输出id和编号的时候，如果你存储是数字，请加上前面补足比如4位整型，%04d，用%d的时候就有问题了，比如0001输出就是1。
10、格式输入了解一下，比如时间"10:20:50"你可以用scanf("%d:%d:%d",&h,&m,&s)。这样可以省去一部分转换的时间。
11、数组开的过大可能会有问题
12、若图比较复杂，使用dfs会爆栈（段错误），此时可以选择bfs。（PAT真题1091）
13、rounded up是四舍五入，不是向上取整。
14、二分法给的数据可能左端比右端大，可以做一下1012就知道了。
15、对数字字符串操作时，要注意数字0端是高位，而不是低位，你可能需要倒转字符串之类的。（PAT真题1024）
16、字符串数字，转换成数字需要去前导零，但是要考虑“0”的情况（PAT整体1038）
17、排序或者二叉树如果没有说明不同，就说明存在有相同的值。
STL总结：
1.vector
#include<iostream> #include<cstdio> #include<vector> using namespace std; void display(vector<int> vi) { for(int i=0;i<vi.size();++i) printf("%d ",vi[i]); printf(" "); } int main() { vector<int> vi; vi.push_back(1); vi.push_back(3); display(vi); //插入 vi.insert(vi.begin()+1,2); display(vi); //删除 vi.erase(vi.begin()+2); display(vi); //清空 vi.clear(); return 0; }
2.queue与priority_queue
#include<iostream> #include<queue> #include<vector> #include<cstdio> using namespace std; int main() { //优先队列会自动排序 priority_queue<int,vector<int>,greater<int> >pq; pq.push(3); pq.push(2); pq.push(1); while(!pq.empty()) { //queue的话是front函数 int data = pq.top(); pq.pop(); printf("%d ",data); } printf(" "); return 0; }
3.map
#include<iostream> #include<cstdio> #include<map> using namespace std; int main() { map<int,int> mii; mii.insert(pair<int,int>(1,1)); mii[2] = 2; printf("删除前：%d ",mii[2]); //删除key=2的值 mii.erase(2); printf("删除后：%d ",mii[2]); return 0; }
4.string
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; int main() { char str[] = "hello world"; string s(str); printf("%s ",s.c_str()); int index = s.find(' '); string s2 = s.substr(0,index); string s3 = s.substr(index+1,s.length()-index-1); printf("%s %s ",s2.c_str(),s3.c_str()); //字符串追加 string newstr = ""; newstr += s2; newstr += "-"; newstr += s3; printf("%s ",newstr.c_str()); //字符串比较 s2 = "aabc",s3="aacc"; printf("%d ",s2.compare(s3)); }
5.set
#include<iostream> #include<cstdio> #include<set> #include<algorithm> using namespace std; void display(char* str,set<int> si) { printf("%s: ",str); set<int>::iterator it = si.begin(); for(;it != si.end();it++) printf("%d ",*it); printf(" "); } int main() { set<int> s1; set<int> s2; s1.insert(1); s1.insert(2); s1.insert(3); s2.insert(3); s2.insert(4); s2.insert(5); s2.insert(6); display("s1",s1); display("s2",s2); //erase的参数是key s2.erase(6); display("s2",s2); set<int> s3,s4; //交集 set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,s3.begin())); //并集 set_union(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s4,s4.begin())); display("交集",s3); display("并集",s4); return 0; }
6、map、set、vector、queue、stack的遍历
#include<iostream> #include<cstdio> #include<vector> #include<set> #include<map> #include<queue> #include<stack> using namespace std; int main() { int n = 10; vector<int> vi; for(int i=0;i<n;++i) vi.push_back(i); printf("vector的遍历:"); for(int i=0;i<n;++i) printf("%d ",vi[i]); puts(""); printf("set的遍历:"); set<int> si; for(int i=0;i<n;++i) si.insert(i); for(set<int>::iterator it=si.begin();it!=si.end();it++) printf("%d ",*it); printf(" map的遍历:"); //map和set的遍历只能用iterator的方式 map<int,int> mii; for(int i=0;i<n;++i) mii[i] = i; for(map<int,int>::iterator it=mii.begin();it!=mii.end();it++) printf("[%d %d] ",it->first,it->second); printf(" queue的遍历:"); //queue和statck遍历只能通过读取和pop的方式 queue<int> qi; //先进先出 for(int i=0;i<n;++i) qi.push(i); while(!qi.empty()) { printf("%d ",qi.front()); qi.pop(); } printf(" stack的遍历:"); stack<int> st; for(int i=0;i<n;++i) st.push(i); while(!st.empty()) { printf("%d ",st.top()); st.pop(); } puts(""); return 0; }
一些树的算法：
如何判断一颗树是完全二叉树，例题可以看PAT1123，可以用一个队列，每次加入一个节点的左右节点，并且pop出该节点，如果该节点为空，则跳出循环，如果该树是完全二叉树，则队列中应该都是null，如果存在非空，就说明不是完全二叉树
bool isCBT(Node* root)
{
queue<Node*> q;
q.push(root);
Node* node;
while(node=q.front())
{
q.push(node->left);
q.push(node->right);
q.pop();
}
while(!q.empty())
{
if(q.front()) return false;
else q.pop();
}
return true;
}
二叉树的层级遍历（非递归）
bool bFirst = true;
void level_travel(Node* root)
{
queue<Node*> q;
q.push(root);
Node* node;
while(!q.empty()&&(node=q.front()))
{
if(bFirst) bFirst = false;
else printf(" ");
printf("%d",node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
q.pop();
}
}
判断图是否遍历所有点以下是错误的例子（PAT1126）
void dfs(int curI,int istep)
{
if(istep==n)
{
flag = true;
return;
}
for(int nextI=1;nextI<=n;++nextI)
{
if(Map[curI][nextI]&&!bVis[nextI])
{
bVis[nextI] = true;
dfs(nextI,istep+1);
}
}
}
如 图
1
3 2 4
从2节点遍历，1,3,4，它的step为2
应该用以下判断：判断sum是否等于顶点个数。
int sum=0;
void dfs(int curI,int istep)
{
++sum;
for(int nextI=1;nextI<=n;++nextI)
{
if(Map[curI][nextI]&&!bVis[nextI])
{
bVis[nextI] = true;
dfs(nextI,istep+1);
}
}
}
如何优化BST搜索的效率，还在思考（当给出一个BST时，当测试数据极端时，二叉树等同于线性结构，此时如何优化搜索效率）。
二叉树的遍历可以看https://www.cnblogs.com/jlyg/p/10354622.html，主要整理了几种二叉树遍历的类型，如已知中序和前序求后序？已知前序和后序求中序？已知中序完全二叉树求广度？已知先序的搜索二叉树求后序？
有时间可以看一下AVL树的模板：https://www.cnblogs.com/jlyg/p/7521434.html
红黑树只要了解性质就好了https://www.cnblogs.com/jlyg/p/10361506.html，实现比较繁琐肯定不考。
其他：
Dijkstra模板：https://www.cnblogs.com/jlyg/p/7404082.html
Pim模板（从没考过）：https://www.cnblogs.com/jlyg/p/10371948.html
并查集的例题：https://www.cnblogs.com/jlyg/p/7356992.html
DFS和BFS肯定是要必会的，这里就不多讲了。DFS注意剪纸就好了，如果map超时就用vector保存路径。