大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
10月份报了PAT甲级,顺便报了Acwing的PAT甲级辅导课,在考试之前汇总下自己刷题的感觉加上必须掌握的知识点
原文链接:PAT甲级备考总结C++
考的链表题一般为要求反转,排序等等之类,最好用数组模拟链表,用链表实现反而麻烦。
栈、队列、哈希表以上可以灵活使用 STL即可解题
树 存储方式利用数组 l[ ],r[ ]存储左孩子右孩子,N为结点个数。
如果题目要求回溯,如判断两个结点是否是兄弟结点等等的题,可以多创建个数组p[ ],表示存储第 i 个下标结点的父亲是p[i]。方便回溯
depth[ ]数组可记录结点 i 的深度,如用于判断两个结点是否属于同一层
floor_num[ ]数组可记录第i层共有多少个结点,在判断完全二叉树或完美二叉树的题目可利用完全二叉树性质 来解题
如该题 A1159 Structure of a Binary Tree
const int N = 1e5;//结点个数
int l[N],r[N];//下标为i 的左儿子为 l[i] 右儿子为r[i]
int p[N];//下标为 i 的父节点为p[i]
int depth[N];//记录结点i的深度
int floor_num[N];//记录第i层共有多少个结点
void init()
{memset(l,-1,sizeof l);
memset(r,-1,sizeof r);
memset(p,-1,sizeof p);
}
建树当题目给权重而非下标序列,如前中序遍历建树,可以将权重映射为下标,再利用下标会简单一些
映射过程#includeunordered_mappos;//记录权重为w的结点的下标为i
int in[N],pre[N],seq[N];//seq存储的是中序遍历的序列 可通过i直接找到权值
int n;//点数
void convert()
{for(int i=0;iin[i] = i;
pos[seq[i]] = i;
}
for(int i=0;i
前序 + 中序//il为中序遍历左端点 ir为右端点 pl为前序遍历左端点 pr为右端点
int build(int il,int ir,int pl,int pr)
{if(pl >pr) return -1;
int k = pre[pl];//k既为root 又为下标
if(il< k) l[k] = build(il,k-1,pl+1,pl+1+k-1-il);
if(k< ir) r[k] = build(k+1,ir,pl+1+k-1-il+1,pr);
return k;
}
中序 + 后序//il为中序遍历左端点 ir为右端点 pl为后序遍历左端点 pr为右端点
int build(int il, int ir, int pl, int pr, int d){if(pl >pr) return -1;
int k = post[pr];
if(il< k) l[k] = build(il, k - 1, pl, pl + k - il - 1, d + 1);
if(k< ir) r[k] = build(k + 1, ir, pl + k - il, pr - 1, d + 1);
return root;
}
遍历
前序遍历 中序遍历 后序遍历通过递归即可
层序遍历void bfs(int root)
{queueq;
vectorv;
q.push(root);
while(q.size())
{int t=q.front();
q.pop();
v.push_back(t);
if(l.count(t)) q.push(l[t]);
if(r.count(t)) q.push(r[t]);
}
for(int i=0;iif(i) cout<<' ';
cout<
AVL数据结构 —— 图解AVL树(平衡二叉树)
考的基本为建树,熟练不平衡时的判断以及调整即可
A1066 Root of AVL Tree
A1123 Is It a Complete AVL Tree
const int N = 30;
int l[N],r[N],v[N],h[N],idx;
void update(int u)
{h[u] = max(h[l[u]],h[r[u]])+1;
}
void R(int& u)
{int p = l[u];
l[u] = r[p];
r[p] = u;
update(u),update(p);
u = p;
}
void L(int& u)
{int p = r[u];
r[u] = l[p];
l[p] = u;
update(u),update(p);
u = p;
}
int get_balance(int u)
{return h[l[u]] - h[r[u]];
}
void insert(int& u,int w)
{if(!u) u = ++idx, v[u] = w;
else if(w< v[u])
{if(!u)
{u = ++idx;
v[u] = w;
}
else if(w< v[u])
{insert(l[u],w);
if(get_balance(u) == 2)
{if(get_balance(l[u] == 1))//LL型
R(u);
else
L(l[u]),R(u);
}
}
else
{insert(r[u],w);
if(get_balance(u) == -2)
{if(get_balance(r[u] == -1))//RR型
L(u);
else
R(r[u]),L(u);
}
}
}
update(u);
}
完全二叉树考的一般都是判断是否为二叉搜索树,可以利用递归判断,从root开始遍历,以左孩子为 2k,右孩子为 2k+1来存放遍历的结果,假设元素个数为n,当递归完二叉树,判断数组序列下标大值,如果大于n则证明该树并非完全二叉树
如该题:A1110 Complete Binary Tree
int maxk,maxid;
void dfs(int u,int k)
{if(u == -1) return;
if(k >maxk)
{maxk = k;
maxid =u;
}
dfs(l[u],k*2);
dfs(r[u],k*2+1);
}
二叉搜索树BST二叉搜索树的性质
通常考的是二叉搜索树的建树与判断是否为二叉搜索树,给前序遍历或者后序遍历来要求你建树。根据性质可以直接sort()给定的序列即得到该树的中序遍历,已经有了两个序列则转化为普通的二叉树建树过程。
最后依据性质来判断即可。
注意点:在find的过程中需要注意路径压缩,否则有一些题目卡测试点
int p[N];
int find(int x)
{if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void Union(int a,int b)
{int pa = find(a),pb = find(b);
if(pa != pb) p[pa] = pb;
}
LCA考的都比较最基本,如果考到了这种需要存储每个结点的父节点
做法:先初始化每个结点的高度,和每个结点的父节点,若两个查询的高度不一样,则先把最低点更新至与另一个结点的高度相同,然后不断向上走,走到公共点则结束
1151 LCA in a Binary Tree
1143 Lowest Common Ancestor
根据给定的顶点数来判断用哪种方式建图,当顶点数大于1e5时则用邻接表来建图
Dijkstra算法以下两种为基础,考难点的还有二维Dijkstra,或者记录路径
朴素版Dijkstra算法利用二维矩阵存储
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra()
{memset(dist, 0x3f, sizeof dist);//在开始的时候需要将所有距离初始化为正无穷
dist[1] = 0;
for (int i = 0; i< n - 1; i ++ )
{int t = -1;
for (int j = 1; j<= n; j ++ )
if (!st[j] && (t == -1 || dist[t] >dist[j]))
t = j;
for (int j = 1; j<= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;//表示不可达
return dist[n];
}
堆优化的Dijkstra算法利用邻接表存储
int dij(int index){s[index] = 0;
priority_queue,greater>hp;
hp.push({0,index});//存储距离 当前点
while(hp.size()){auto t = hp.top();
hp.pop();
int v = t.second;
if(st[v]) continue;
st[v] = true;
for(int u = 0; u< g[v].size(); u ++ ){int c = g[v][u].first;
int dis = g[v][u].second;
if(!st[c] && s[v] + dis< s[c]){s[c] = s[v] + dis;
hp.push({s[c],c});
}
}
}
if(s[n] == inf) return -1;
return s[n];
}
其他如拓扑序列等等
数学知识 大公约数 最小公倍数例如在PAT甲级的一些题里面要求有理数加减乘除,分式加减乘除,化简的时候gcd是必不可少的。可以直接调用algorithm库里的gcd函数来求大公约数,同时可求出最小公倍数。
#include#include
using namespace std;
int lcm(int a, int b)
{return a * b / __gcd(a, b);
}
int main()
{int a,b;
cin>>a>>b;
cout<<__gcd(a,b)<
筛质数–求1~N的所有质数利用欧拉筛法
const int N= 1e6 + 10;
int primes[N], cnt;//primes[]存储的是1~N的所有质数
bool st[N];
void get_primes(int n)
{for(int i=2;i<=n;i++)
{if(!st[i])
{primes[cnt++]=i;
}
for(int j=0;primes[j] * i<= n ;j++)
{st[primes[j] * i ] = true;
if(i % primes[j]==0) break;
}
}
}
判断是否为质数如求A1096 Consecutive Factors连续因子或分解质因数的题会用到。
注意循环过程最好使用 i<= x / i,用i * i<= x在i很大的时候可能会爆 int,用sqrt(x) 时每次都需要开次方速度反而慢
bool is_prime(int x)
{if(x<2) return false;
for(int i=2;i<=x/i;i++)
if(x%i==0)
return false;
return true;
}
常用库函数均在cmath库里
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧