算法训练34

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;
}

3. 参考资料

1145. Hashing – Average Search Time (25) – 甲级_柳婼的博客-CSDN博客