算法训练23

1. 知识点总结

本次模拟得分96/100,卡在了树结构上

题目	得分	难度
General Palindromic Number	20	🎈
Tree Traversals	25	🎈
Deepest Root	24/25	🎈🎈
Digital Library	30	🎈

2. 分题题解

2.1 General Palindromic Number

回文判别+进制转换，属于大一C++基础，没有难度和坑

需要注意的是转换后每个位保存在vector中，因为radix的值比较大，超过36了

#include<bits/stdc++.h>
using namespace std;
int num,radix;
//将数字按照指定的Index转化
vector<int>ans;
int len;
void change(int num,int index){
	while(num){
		ans.push_back(num%index);
		num/=index;
	}
	return;
} 
bool isPalindromic(){
	len=ans.size();
	for(int i=0;i<len/2;i++){
		if(ans[i]!=ans[len-i-1]){
			return false;
		}
	}
	return true;
}
int main(){
	scanf("%d%d",&num,&radix);
	change(num,radix);
	if(isPalindromic()){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	for(int i=len-1;i>=0;i--){
		if(i!=len-1){
			printf(" ");
		}
		printf("%d",ans[i]);
	}
	return 0;
} 

2.2 Tree Traversals

根据后序遍历和中序遍历得到树结构再层序输出：

属于数据结构基础题，也是板子题

#include<bits/stdc++.h>
using namespace std;
//给出后序遍历和中序遍历，输出层次遍历的结果
int n;
vector<int>pos;
vector<int>in; 
struct node{
	int val;
	node* left=NULL;
	node* right=NULL;
};
node* build(int posL,int posR,int inL,int inR){
	if(posL>posR||inL>inR){
		return NULL;
	}
	int k;
	int val=pos[posR];
	for(int i=inL;i<=inR;i++){
		if(in[i]==val){
			k=i;
			break;
		}
	}
	int Left_len=k-inL;
	
	node*root=new node;
	root->val=val;
	root->left=build(posL,posL+Left_len-1,inL,k-1);
	root->right=build(posL+Left_len,posR-1,k+1,inR);
	
	return root;
}
void levelTravel(node* root){
	queue<node*>q;
	q.push(root);
	bool flag=false;
	while(!q.empty()){
		node* top=q.front();
		q.pop();
		if(!flag){
			flag=true;
		}else{
			printf(" ");
		}
		printf("%d",top->val);
		if(top->left!=NULL){
			q.push(top->left);
		}
		if(top->right!=NULL){
			q.push(top->right);
		}
	}
	return ;
} 
int main(){
	scanf("%d",&n);
	pos.resize(n);
	in.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&pos[i]);
	}
	for(int i=0;i<n;i++){
		scanf("%d",&in[i]);
	}
	node* root=build(0,n-1,0,n-1);//建立树 
	levelTravel(root);//层次遍历 
	return 0;
}

2.3 Deepest Root

订正过又忘了……超时＋错误

#include<bits/stdc++.h>
using namespace std;
//以某个结点作为根结点，找到对应的叶子结点
//计算以叶子结点作为根之后的最大深度
vector<vector<int> >graph; 
vector<bool>vis; 
int cnt=0;
int n;
int u,v;
int max_level=-1;
set<int>ans;
void dfs(int id,int level){
	vis[id]=true;
	for(int i=0;i<graph[id].size();i++){
		if(!vis[graph[id][i]]){
			dfs(graph[id][i],level+1);
		}
	}
	return;
}
void dfs2(int id,int level,int root){
	vis[id]=true;
	bool flag=false;
	for(int i=0;i<graph[id].size();i++){
		if(!vis[graph[id][i]]){
			dfs2(graph[id][i],level+1,root);
			flag=true;
		}
	}
	if(!flag){
		if(level>max_level){
			max_level=level;
			ans.clear();
			ans.insert(root);
		}else if(level==max_level){
			ans.insert(root);
		}
	}
	return;
}
int main(){
	scanf("%d",&n);
	graph.resize(n+1);
	vis.resize(n+1);
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&u,&v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}	
	//首先判断是不是一棵树
	fill(vis.begin(),vis.end(),false);
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			cnt++;
			dfs(i,0);
		}
	}
	if(cnt!=1){
		printf("Error: %d components",cnt);
	}else{
		for(int i=1;i<=n;i++){
			if(graph[i].size()==1){
				fill(vis.begin(),vis.end(),false);
				dfs2(i,0,i);
			}
		} 
		
		for(set<int>::iterator it=ans.begin();it!=ans.end();it++){
			printf("%d\n",*it);
		}
	}
	return 0;
}

2.4 Digital Library

结构体的简单应用，同时复习了find+vector写法;难度不敌前一题

#include<bits/stdc++.h>
using namespace std;
struct Book{
	string id;
	string title;
	string author;
	vector<string>keywords;
	string publisher;
	string date;
};
int n,m;
int op;
string temp;
string query;
vector<Book>books;
string str;
bool cmp(Book a,Book b){
	return a.id<b.id;
}
int main(){
	scanf("%d",&n);
	books.resize(n);
	getchar();
	for(int i=0;i<n;i++){
		getline(cin,books[i].id);
		getline(cin,books[i].title);
		getline(cin,books[i].author);
		getline(cin,str);
		//将关键词拆解
		temp="";
		str+=" ";
		for(int k=0;k<str.length();k++){
			if(str[k]==' '){
				if(temp!=""){
					books[i].keywords.push_back(temp);
					temp="";
				}
			}else{
				temp+=str[k];
			}
		} 
		getline(cin,books[i].publisher);
		getline(cin,books[i].date);
	}
	scanf("%d",&m);
	sort(books.begin(),books.end(),cmp);
	bool flag=false;

	for(int i=0;i<m;i++){
		scanf("%d: ",&op);
		getline(cin,str);
		flag=false;
		printf("%d: ",op);
		cout<<str<<"\n";
		if(op==1){
			//按照标题找 
			for(int i=0;i<n;i++){
				if(books[i].title==str){
					flag=true;
					cout<<books[i].id<<"\n";
				}
			}
		}else if(op==2){
			//按照作者找 
			for(int i=0;i<n;i++){
				if(books[i].author==str){
					flag=true;
					cout<<books[i].id<<"\n";
				}
			}
		}else if(op==3){
			//按照关键字找
			for(int i=0;i<n;i++){
				if(find(books[i].keywords.begin(),books[i].keywords.end(),str)!=books[i].keywords.end()){
					flag=true;
					cout<<books[i].id<<"\n";
				}
			}
		}else if(op==4){
			//按照出版商找 
			for(int i=0;i<n;i++){
				if(books[i].publisher==str){
					flag=true;
					cout<<books[i].id<<"\n";
				}
			}
		}else{
			//按照年份找
			for(int i=0;i<n;i++){
				if(books[i].date==str){
					flag=true;
					cout<<books[i].id<<"\n";
				}
			}
		} 
		if(!flag){
			cout<<"Not Found\n";
		}
	}
	
	
	return 0;
}