数据结构与算法复习：第七弹

文章目录

1. 知识点总结
2. 分题题解
3. 参考资料

1. 知识点总结

100/100,压着点写完的，中途打断了一下但是计时没终止，心惊肉跳的模拟……呜呜呜，加油加油，只希望最后不要爆零就好。

这次的题目总体平缓，没有特别难的，也没有那种很轻松一下子就过的。尤其最后一题还是考察的蛮碎的。

题目	难度	知识点
1156 Sexy Primes	🎯	数学
1157 Anniversary	🎯	结构体STL
1158 Telefraud Detection	🎯	并查集
1159 Structure of a Binary Tree	🎯🎯	二叉树，遍历，字符串操作

2. 分题题解

2.1 PAT 1156 Sexy Primes

数学+简单的条件限制时间复杂度,条件限制不加的话会超时几个测试点;

关键词:素数判别

#include
using namespace std;
int num1,num2;
bool isPrime(int x){
	if(x<=1)return false;
	if(x==2||x==3||x==5||x==7||x==11){
		return true;
	}
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}
bool flag=false;
int main(){
	scanf("%d",&num1);
	if(isPrime(num1)){
		if(isPrime(num1-6)){
			printf("Yes\n%d",num1-6);
			flag=true;
		}else if(isPrime(num1+6)){
			printf("Yes\n%d",num1+6);
			flag=true;
		}
	} 
	if(!flag){
		while(1){
			num1++;
			if(isPrime(num1)&&(isPrime(num1+6)||isPrime(num1-6))){
				printf("No\n%d",num1);
				break;
			}
		}
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2.2 PAT 1157 Anniversary

基础的结构体，不能完全说是水题，考察的是英语阅读理解，没错，卡在了English上，但是还是机智的很快反应过来（偶吼吼~

#include
using namespace std;
int N;//id个数 
int M;//参会id个数 
map<string,bool>isAl;
string id;
struct Vistor{
	string id;
	string birth;
	int isok=0;
};
vector<Vistor>vis;
bool cmp(Vistor a,Vistor b){
	if(a.isok!=b.isok){
		return a.isok>b.isok;
	}else{
		return a.birth<b.birth;
	}
}
int ans=0;
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		cin>>id;
		isAl[id]=true;
	}
	scanf("%d",&M);
	vis.resize(M);
	for(int i=0;i<M;i++){
		cin>>id;
		vis[i].id=id;
		vis[i].birth=id.substr(6,8);
		if(isAl.find(id)!=isAl.end()){
			vis[i].isok=1;
			ans++;
		}
	}
	printf("%d\n",ans);
	sort(vis.begin(),vis.end(),cmp);
	printf("%s",vis[0].id.c_str());
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2.3 PAT 1158 Telefraud Detection

这题题解写得不是很漂亮，主要是数据量不大，否则我觉得我的解法好像开的空间有点多了……

基本的并查集板子，外面套了一层判断，也就是需要先排除可疑人物再对可疑人物的关系网做一个并查集

#include
using namespace std;
//首先筛出可疑人员，再找到gang
int K,N,M;//K是阈值，N是人数，M是电话数
vector<vector<int>>graph; 
vector<int>suspect;
vector<bool>isSus;
vector<int>f;
vector<set<int>>ans;
void init(){
	for(int i=1;i<=N;i++){
		f[i]=i;
		ans[i].insert(i);
	}
}
int Find(int a){
	int x=a;
	while(a!=f[a]){
		a=f[a];
	}
	int temp;
	while(x!=f[x]){
		temp=f[x];
		f[x]=a;
		x=temp;
	}
	return a;
}
int Union(int a,int b){
	int fa=Find(a);
	int fb=Find(b);
	if(fa<fb){
		f[fb]=fa;//B合并给A 
		//printf("以%d为根的合并到%d\n",fb,fa);
		for(set<int>::iterator it=ans[fb].begin();it!=ans[fb].end();it++){
			ans[fa].insert(*it);
		}
		ans[fb].clear();
	}else if(fb<fa){
		f[fa]=fb;//A合并给B 
		//printf("以%d为根的合并到%d\n",fa,fb);
		for(set<int>::iterator it=ans[fa].begin();it!=ans[fa].end();it++){
			ans[fb].insert(*it);
		}
		ans[fa].clear();
	}
}
int u,v,d;
int main(){
	scanf("%d%d%d",&K,&N,&M);
	graph.resize(N+1);
	isSus.resize(N+1);
	ans.resize(N+1);
	f.resize(N+1);
	fill(isSus.begin(),isSus.end(),false);
	for(int i=1;i<=N;i++){
		graph[i].resize(N+1);
		fill(graph[i].begin(),graph[i].end(),0);
	}
	for(int i=0;i<M;i++){
		scanf("%d%d%d",&u,&v,&d);
		//call-receive
		graph[u][v]+=d; 
	}
	//首先筛查出可疑人员:A->B的短电话
	for(int i=1;i<=N;i++){
		int call=0;//打出去的短电话个数
		int callback=0;//回复的电话
		for(int j=1;j<=N;j++){
			if(j==i||graph[i][j]==0){
				continue;
			}else if(graph[i][j]<=5){
				call++;
				if(graph[j][i]){
					callback++;
				}
			}
		}
		if(call>K&&callback<=call*0.2){
			suspect.push_back(i);
			isSus[i]=true;
		}
	} 
	if(suspect.size()==0){
		printf("None");
	}else{
		//下面并查集求犯罪集合
		init();
		int len=suspect.size();
		for(int i=0;i<len;i++){
			for(int j=i+1;j<len;j++){
				int a=suspect[i];
				int b=suspect[j];
				if(graph[a][b]&&graph[b][a]){
					Union(a,b);
				}
			}
		}
		//输出结果
		for(int i=0;i<len;i++){
			int id=suspect[i];
			if(ans[id].size()){
				bool flag=false;
				for(set<int>::iterator it=ans[id].begin();it!=ans[id].end();it++){
					if(flag){
						printf(" ");
					}else{
						flag=true;
					}
					printf("%d",*it);
				}
				printf("\n");
			}
		}
	}
	 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

2.4 PAT 1159 Structure of a Binary Tree

重新复习了字符串的输入和提取值操作~总体不难，fullTree的定义注意读题，和书上定义有区别嗷！

关键词：二叉树构建，层次遍历

#include
using namespace std;
int N,M;
vector<int>post,in; 
string str;
struct Node{
	int val;
	Node*left=NULL,*right=NULL;
	int level=0;
	Node*parent=NULL;
};
map<int,Node*>mp;
//构建二叉树 
bool isFull=true;
Node* build(int inL,int inR,int postL,int postR){
	if(inL>inR||postL>postR||inL<0||inR>=N||postL<0||postR>=N){
		return NULL;
	}
	Node *root=new Node;
	root->val=post[postR];
	int k;
	for(k=inL;k<=inR;k++){
		if(in[k]==root->val){
			break;
		}
	}
	int num=k-inL;
	root->left=build(inL,k-1,postL,postL+num-1);
	root->right=build(k+1,inR,postL+num,postR-1);
	return root;
}
//层序遍历
vector<int>cnt;//每一层的结点个数 
int max_level=0;
void levelTravel(Node*root){
	queue<Node*>q;
	q.push(root);
	while(!q.empty()){
		Node*top=q.front();
		int l=top->level;
		mp[top->val]=top;
		cnt[l]++;
		max_level=top->level;
		//printf("level:%d val:%d\n",l,top->val);
		q.pop();
		if(top->left==NULL&&top->right!=NULL){
			isFull=false;
		}
		if(top->left!=NULL&&top->right==NULL){
			isFull=false;
		}
		if(top->left){
			q.push(top->left);
			top->left->parent=top;
			top->left->level=l+1;
		}
		if(top->right){
			q.push(top->right);
			top->right->parent=top;
			top->right->level=l+1;
		}
	}
} 
int main(){
	scanf("%d",&N);
	post.resize(N);
	in.resize(N);
	cnt.resize(N+1);
	fill(cnt.begin(),cnt.end(),0); 
	for(int i=0;i<N;i++){
		scanf("%d",&post[i]);
	}
	for(int i=0;i<N;i++){
		scanf("%d",&in[i]);
	}
	//构建树
	Node *root=build(0,N-1,0,N-1);
	levelTravel(root); 
	scanf("%d",&M);
	getchar();
	for(int i=0;i<M;i++){
		getline(cin,str);
		int len=str.length();
		if(str[len-1]=='t'){
			//A is the root
			int val;
			sscanf(str.c_str(),"%d is the root",&val);
			if(root->val==val){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}else if(str[len-1]=='s'){
			//A and B are siblings
			int a,b;
			sscanf(str.c_str(),"%d and %d are siblings",&a,&b);
			if(mp[a]->parent!=NULL&&mp[b]->parent!=NULL&&mp[a]->parent->val==mp[b]->parent->val){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}else if(str[len-1]=='l'){
			//A and B are on the same level
			int a,b;
			sscanf(str.c_str(),"%d and %d are on the same level",&a,&b);
			if(mp[a]->level==mp[b]->level){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}else if(str[len-1]=='e'){
			//It is a full tree
			//满二叉树的定义？ 
			if(isFull){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}else if(find(str.begin(),str.end(),'p')!=str.end()){
			//A is the parent of B
			int a,b;
			sscanf(str.c_str(),"%d is the parent of %d",&a,&b);
			if(mp[b]->parent!=NULL&&mp[b]->parent->val==a){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}else if(find(str.begin(),str.end(),'g')!=str.end()){
			//A is the right child of B
			int a,b;
			sscanf(str.c_str(),"%d is the right child of %d",&a,&b);
			if(mp[b]->right!=NULL&&mp[b]->right->val==a){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}else if(find(str.begin(),str.end(),'f')!=str.end()){
			//A is the left child of B
			int a,b;
			sscanf(str.c_str(),"%d is the left child of %d",&a,&b);
			if(mp[b]->left!=NULL&&mp[b]->left->val==a){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}
		
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

3. 参考资料

无，闭卷

相关阅读:
【C++初阶】C++入门(一)
手把手推导分布式矩阵乘的最优并行策略
 椭圆曲线算法
 LeetCode 2034. 股票价格波动：哈希表 + 有序集合
 Django微信点餐小程序设计与实现计算机专业毕业设计源码55380
linux 查看CPU架构是AMD还是ARM
软件项目管理 6.7.参数估算法
 流畅的Python读书笔记(五)序列：序列的排序及管理
 京东数据分析报告：2023年10月京东平台大家电销售数据汇总分析
 d的整与nan
原文地址：https://blog.csdn.net/qq_45751990/article/details/126077415