目录 写在前面必备信息PAT考点解题技巧类型转换使用unordered_map关于大小写转换常用库函数 解题模板排序选择排序插入排序归并排序快速排序堆排序拓扑排序 求最大公约数并查集最短路径
写在前面
笔者考PAT也有两次了，但属实太菜，没拿满分。但这几个月下来不断练习，也积累了点经验，就分享给大家。
必备信息PTA
刷题平台，有历年乙级、甲级考试真题，支持在线评测。
需要注意：
PAT
PAT报名网址，平常一些关于考试的最新资讯也在上面哦~
真题分类
PAT甲级题目及分类总结，建议刷题时第一遍先按分类刷，知道每个考点套路是什么，第二遍再按顺序刷。
必备书籍：算法笔记，零基础的同学看了能快速上手，里面也有各种PAT解题技巧。（需要电子版的可以留个邮箱，有空发给你们~）
解题没有思路时可以去看看一些魁梧的银耳汤的博客，会分享最优的思路：过时的皮皮虾（热情的小笼包）PAT甲级题目链接
乙级：中文题目，最难只到排序算法
甲级：英文题目，考点涉及基本数据结构，图，树，动态规划等等
（记得官网上有写的，一时半会儿找不到了。。）
一些基本的读入数据，字符串截取，各种类型转换还是要掌握熟练的。（万一理解了整个题目，却拿不到想要的数据就尴尬了哈哈）
类型转换 char 转 int char c = '0';int i = c - '0'; // 0 int 转 char int i = 5;char c= i + '0'; // 5 char数组 转 int char ch[3]="12";int n=atoi(ch); int 转 char数组 //用 char * itoa(int _Val,char *_DstBuf,int _Radix)//_Val:要转换的int值//_Radix:使用的进制int n=10;char ch[10];itoa(n,ch,2);//1010itoa(n,ch,10);//10 int 转 string //1.to_string()string s;s=to_string(1234);//2.或者借助字符串流//导入#include<sstream>int n=10;string s;stringstream ss;ss<<n;s=ss.str(); string 转 int //1.先转换为char数组，再利用atoi//2.借助字符串流istringstream is("12"); int i;is >> i;//3.int i=stoi("123"); 使用unordered_map对不需要排序的数据，用unordered_map代替map，提高效率
关于大小写转换对char数组来说，PAT中无法使用strupr()和strlwr() 。pat中无法使用该函数！！！
char c[3]="ab";strupr(c);printf("%s",c);//ABstrlwr(c);printf("%s",c);//ab只能自己手写一个
for(int i=0;i<strlen(s);i++){if(s[i]>='A'&&s[i]<='Z'){s[i]=tolower(s[i]);//转换大写为toupper//s[i]+=32;//+32转换为小写//s[i]=s[i]-'A'+'a';}} 常用库函数当然还得学会用一些常用库函数，对优化代码，节省时间很有帮助。
就不整理了，自己点进去看吧
一些算法的模板是必背的，但是要在理解的基础上熟记，明白这类算法是用来解决什么问题的。这里总结的模板基本上是算法笔记上的，如果大家不理解的可以仔细看看书。
排序 选择排序每轮选择一个最小的值。
void selectSort(int a[],int n){ for (int i = 0; i < n - 1; ++i) { int u=i; for (int j = i+1; j < n; ++j) { if(a[u]>a[j]) u=j; } swap(a[i],a[u]); }} 插入排序 void insertSort(int a[],int n){ for (int i = 1; i < n; ++i) { for (int j = i; j > 0; --j) { if(a[j-1]>a[j]) swap(a[j-1],a[j]); } }} 归并排序 void Merge(int a[],int l1,int r1,int l2,int r2){ int temp[10]; int pos=0,i=l1,j=l2; while(i<=r1&&j<=r2){ if(a[i]<a[j]){ temp[pos++]=a[i++]; }else{ temp[pos++]=a[j++]; } } while(i<=r1){ temp[pos++]=a[i++]; } while(j<=r2){ temp[pos++]=a[j++]; } for (int k = 0; k < pos; ++k) { a[l1+k]=temp[k]; }}//非递归void mergeSort(int a[],int n){ for (int step = 2; step/2<n; step*=2) { for (int i = 0; i < n; i+=step) { int mid=i+step/2-1; Merge(a,i,mid,mid+1,min(n-1,mid+step/2)); } printf("step:%d ",step); printNum(a,n); }}//递归void mergeSort2(int a[],int l,int r){ if(l<r){ int mid=(l+r)/2; mergeSort2(a,l,mid); mergeSort2(a,mid+1,r); Merge(a,l,mid,mid+1,r); }} 快速排序 int Partition(int a[],int l,int r){ int temp=a[l]; while(l<r){ while(l<r&&a[r]>temp) r--; a[l]=a[r]; while(l<r&&a[l]<temp) l++; a[r]=a[l]; } a[l]=temp; return l;}void quickSort(int a[],int l,int r){ if(l<r){ int p=Partition(a,l,r); quickSort(a,l,p-1); quickSort(a,p+1,r); }} 堆排序 void downAdjust(int a[],int low,int high){ int i=low,j=2*i; while(j<=high){ if(j+1<=high&&a[j+1]>a[j]) j=j+1; if(a[j]>a[i]){ swap(a[j],a[i]); i=j; j=2*i; }else break; }}void heapSort(int a[],int n){ for (int i = n/2; i >=1; --i) { downAdjust(a,i,n); } for (int i = n; i > 1 ; --i) { swap(a[1],a[i]); downAdjust(a,1,i-1); }} 拓扑排序重要应用——判断一个给定的图是否是有向无环图
//拓扑排序 const int MAXV=100;vector<int>G[MAXV];int n,m,inDegree[MAXV];//inDegree[]记录每个结点的入度bool topologicalSort(){ int num=0; queue<int> q; for (int i = 0; i < n; ++i) { if(inDegree[i]==0){ q.push(i); } } while(!q.empty()){ int u=q.front(); q.pop(); for (int i = 0; i < G[u].size(); ++i) { int v=G[u][i]; inDegree[v]--; if(inDegree[v]==0){ q.push(v); } } G[u].clear(); num++; } if(num==n) return true; else return false;} 求最大公约数a%b如果为0，则取b作为最大公约数，否则用b作为被除数，a%b作为除数，继续求余数。
long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b);} 并查集 int father[maxn];int findFather(int a){ int x=a; while (father[a]!=a){ a=father[a]; } //路径压缩 while(x!=a){ int z=father[x]; father[x]=a; x=z; } return a;}void Union(int a,int b){ int fa=findFather(a); int fb=findFather(b); if(fa!=fb){ father[fb]=fa; }} 最短路径经典的迪杰斯特拉
void dijkstra(int s){ fill(d,d+maxn,INF); d[s]=0; for (int i = 0; i < n; ++i) { int u=-1,MIN=INF; for (int j = 0; j < n; ++j) { if(!vis[j]&&d[j]<MIN){ MIN=d[j]; u=j; } } if(u==-1) return; vis[u]= true; for (int v = 0; v < n; ++v) { if(!vis[v]&&G[u][v]!=INF){ if(d[u]+G[u][v]<d[v]){ d[v]=d[u]+G[u][v]; } } } }}