1. 知识点总结
93/100(2h),卡在了第二题的哈希表的题目,因为遇到的次数不太多,但是印象中遇到的时候都没做出来……
题目 | 难度 | 知识点 |
---|---|---|
1144 The Missing Number | 🎯 | STL排序+数组 |
1145 Hashing - Average Search Time | 🎯🎯|🐸 | 哈希表 |
1146 Topological Order | 🎯 | 图论:拓扑排序 |
1147 Heaps | 🎯 | 堆+二叉树 |
2. 分题题解
2.1 PAT 1144 The Missing Number
比较基础的题目,如代码,所见即所得~
首先将数组排序,ans默认为1,遇到相等的ans++,最后ans的值即为输出
#include<bits/stdc++.h>
using namespace std;
int N;
//输出最小的被遗忘的正数
vector<int>v;
int main(){
scanf("%d",&N);
v.resize(N);
int ans=1;
for(int i=0;i<N;i++){
scanf("%d",&v[i]);
}
sort(v.begin(),v.end());
for(int i=0;i<N;i++){
if(v[i]==ans){
ans++;
}
}
printf("%d",ans);
return 0;
}
2.2 PAT 1145 Hashing - Average Search Time
只过了两个测试点,get-18分,主要是自己对于题干中Quadratic probing (with positive increments only) is used to solve the collisions.的英文理解不到位,只知道是二次探查法,具体的编程细节推理是有问题的,参考了柳神的代码订正了一下。
第一版,自己的18/25:
#include<bits/stdc++.h>
using namespace std;
int MSize,N,M;
int num;
vector<int>table;//哈希表
int temp;
double sum=0;//消耗的搜索时间
bool isPrime(int x){
if(x<=1)return false;
if(x==2||x==3||x==5||x==7){
return true;
}
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
int main(){
scanf("%d%d%d",&MSize,&N,&M);
while(!isPrime(MSize)){
MSize++;
}
table.resize(MSize);
fill(table.begin(),table.end(),-1);
for(int i=0;i<N;i++){
scanf("%d",&num);
//试着插入
bool flag=false;
int pos=num%MSize;
int add=0;
while(1){
int npos=pos+add*add;
if(npos>=MSize){
break;
}
if(table[npos]==-1){
table[npos]=num;
flag=true;
break;
}
add+=1;
}
if(!flag){
printf("%d cannot be inserted.\n",num);
}
}
for(int i=0;i<M;i++){
scanf("%d",&temp);
//尝试寻找
int pos=temp%MSize;
int add=0;
int cnt=0;
while(1){
int npos=pos+add*add;
cnt++;
//printf("pos:%d\n",npos);
if(npos>=MSize){
break;
}
if(table[npos]==temp){
break;
}
add+=1;
}
sum+=cnt;
//printf("%d消耗查找:%d\n",temp,cnt);
}
//输出平均搜索时间
printf("%.1f",(sum+1)/M);
return 0;
}
第二版:订正
二次探查:Quadratic probing (with positive increments only)
范围是
(0≤j≤tSize)
,遍历的时候pos=(num+j×j)%tSize
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int x){
if(x<=1)return false;
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
int N,M,t;
int num,temp;
double sum=0;
int main(){
scanf("%d%d%d",&t,&N,&M);
while(!isPrime(t)){
t++;
}
vector<int>table(t,-1);
for(int i=0;i<N;i++){
scanf("%d",&num);
//插入数字到哈希表
bool flag=false;
for(int j=0;j<=t;j++){//注意范围
int pos=(num+j*j)%t;
if(table[pos]==-1){
flag=true;
table[pos]=num;
break;
}
}
if(!flag){
printf("%d cannot be inserted.\n",num);
}
}
for(int i=0;i<M;i++){
scanf("%d",&temp);
int cnt=0;
for(int j=0;j<=t;j++){//注意范围
cnt++;
int pos=(temp+j*j)%t;
if(table[pos]==temp||table[pos]==-1){
break;
}
}
sum+=cnt;
}
printf("%.1f",sum/M);
return 0;
}
2.3 PAT 1146 Topological Order
基础题:拓扑排序的题目,没有卡时间复杂度,对于输入的数组判断是否是拓扑序列,只要每次判断当前结点的先序结点数量是否为0,若不为0则该序列不是拓扑序列,若是则更新以当前结点为先序结点的结点们的pre值
#include<bits/stdc++.h>
using namespace std;
//判断一个序列是否是拓扑序列
int N,M,K;
vector<int>q;
vector<int>pre;//记录前序个数
vector<vector<int>>tail;
vector<int>ans;
int u,v;
int main(){
scanf("%d%d",&N,&M);
tail.resize(N+1);
pre.resize(N+1);
fill(pre.begin(),pre.end(),0);
for(int i=0;i<M;i++){
scanf("%d%d",&u,&v);
tail[u].push_back(v);
pre[v]++;
}
scanf("%d",&K);
q.resize(N);
for(int i=0;i<K;i++){
//输入询问序列
for(int j=0;j<N;j++){
scanf("%d",&q[j]);
}
//判断是否是拓扑序列
vector<int>npre=pre;
for(int j=0;j<N;j++){
int id=q[j];
if(npre[id]!=0){
ans.push_back(i);
break;
}else{
for(int c=0;c<tail[id].size();c++){
npre[tail[id][c]]--;
}
}
}
}
//输出答案
for(int i=0;i<ans.size();i++){
if(i)printf(" ");
printf("%d",ans[i]);
}
return 0;
}
2.4 PAT 1147 Heaps
主要是考数组存储的堆、二叉树的性质,包括对于后序遍历的输出以及大顶堆-小顶堆的判断,之前考过类似的,关键在于对于数组索引之间关系的探索。
虽然是最后一题,但是属于基础题。
#include<bits/stdc++.h>
using namespace std;
//判断一个堆,输出其后序遍历的结果
int M,N;
vector<int>nodes;
bool flag;
void PostTravel(int root){
if(root<0||root>=N){
return;
}
PostTravel((root+1)*2-1);
PostTravel((root+1)*2);
if(flag){
printf(" ");
}else{
flag=true;
}
printf("%d",nodes[root]);
}
int type;//1-Max -1-Min 0-Not
vector<int>temp;
//判断堆
void solution(int root,vector<int>path){
if(type==0){
return;
}
if(root>=N){
//没法再加了
for(int i=1;i<path.size();i++){
if(path[i]<path[i-1]&&type==-1){
type=0;
break;
}
if(path[i]>path[i-1]&&type==1){
type=0;
break;
}
}
}else{
path.push_back(nodes[root]);
solution((root+1)*2-1,path);
solution((root+1)*2,path);
}
}
int main(){
scanf("%d%d",&M,&N);
nodes.resize(N);
while(M--){
for(int i=0;i<N;i++){
scanf("%d",&nodes[i]);
}
//判断:因为是distinct所以可以直接得到结果
if(nodes[0]>nodes[1]){
type=1;
}else{
type=-1;
}
solution(0,temp);
if(type==1){
printf("Max Heap\n");
}else if(type==-1){
printf("Min Heap\n");
}else{
printf("Not Heap\n");
}
//输出
flag=false;
PostTravel(0);
printf("\n");
}
return 0;
}