当前位置：网站首页>PTA class a simulation bomb 10: 1119-1123

PTA class a simulation bomb 10: 1119-1123

2022-06-26 01:43:00 【Republic cake】

1. Summary of knowledge points

Skip the one you wrote ~
This assignment , The knowledge involved is ：

  • STL
  • Binary tree （ In the following order + Before the order ）
  • AVL Binary balance tree

Because it's a good question , So sort according to the difficulty score

Question no difficulty Question type
1120set Basics
1121map The key value determines whether there is
1119 Format giant pit , Before the order + The following sequence outputs the middle sequence , Can deduce the idea of solving problems according to the data structure
1123** emphasize AVL Trees ,** I don't feel much about the exam , But I can't beat them blindly , Baa ！

2. Sub topic solution

2.1 The first question is ：1120 Friend Numbers (20 branch )

【 Subject portal 】

Simple questions , It was used set, So you don't have to reorder yourself 

#include<bits/stdc++.h>
using namespace std;
int N;
vector<int>num;
set<int>fid;

int countDigit(int x){
    
	int sum=0;
	while(x){
    
		sum+=x%10;
		x/=10;
	}
	return sum;
}
int main(){
    
	scanf("%d",&N);
	num.resize(N);
	for(int i=0;i<N;i++){
    
		scanf("%d",&num[i]);
		int sum=countDigit(num[i]);
		fid.insert(sum);
	}
	printf("%d\n",fid.size());
	for(set<int>::iterator it=fid.begin();it!=fid.end();it++){
    
		if(it!=fid.begin()){
    
			printf(" ");
		}
		printf("%d",*it);
	}
	return 0;
}

2.2 The second question is ：1121 Damn Single (25 branch )

【 Subject portal 】

twitter ： good heavens , Title learned , Don't go out next time , Have been offended to

  • We are looking at basic graph theory , Check M Among the guests, those who are single or married but their spouses are not present

  • set Storage avoids following ID The trouble of ascending sort

Simple questions , I've met before 

#include<bits/stdc++.h>
using namespace std;
int N;
int M;
map<int,int>couple;
map<int,bool>iscome;
set<int>dog;
set<int>guest;
int a,b,id;
int main(){
    
	scanf("%d",&N);
	for(int i=0;i<N;i++){
    
		scanf("%d%d",&a,&b);
		couple[a]=b;
		couple[b]=a;
	}
	scanf("%d",&M);
	for(int i=0;i<M;i++){
    
		scanf("%d",&id);
		guest.insert(id);
		iscome[id]=true;
	}
	for(set<int>::iterator it=guest.begin();it!=guest.end();it++){
    
		if(couple.count(*it)==0){
    // There are no lovers  
			dog.insert(*it);
		}else if(!iscome[couple[*it]]){
    // There are lovers but the lovers are not here  
			dog.insert(*it);
		}
	}
	printf("%d\n",dog.size());
	for(set<int>::iterator it=dog.begin();it!=dog.end();it++){
    
		if(it!=dog.begin()){
    
			printf(" ");
		}
		printf("%05d",*it);
	}
	
	return 0;
}

2.3 Third question ：1119 Pre- and Post-order Traversals (30 branch )

【 Subject portal 】

Crazy , The format error that has been stuck for an hour bursts to zero , The result is a final output printf("\n"), It's numb

  • Note the final output printf("\n")
  • The case of multiple solutions is preR-preL+1==2 When , There is no way to determine whether it is left or right 
#include<bits/stdc++.h>
using namespace std;
int N;
bool flag=true;
vector<int>pre;
vector<int>post;
struct Node{
    
	int val;
	Node *left=NULL;
	Node *right=NULL;
};
//Yes--- only 
//No---  Is not the only  
Node *build(int preL,int preR,int postL,int postR){
    
	// Print every time 
// printf("post:");
// for(int i=postL;i<=postR;i++)printf("%d ",post[i]); 
// printf("\n pre:");
// for(int i=preL;i<=preR;i++)printf("%d ",pre[i]); 
// printf("\n");
// printf("postnum%d prenum%d\n",postR-postL+1,preR-preL+1);
	
	if(preR-preL+1==2&&postR-postL+1==2){
    
		flag=false;
	}
	if(preR<preL){
    
		return NULL;
	}else if(preR==preL){
    
		Node *root=new Node;
		root->val=pre[preL];
		return root;
	}
	// Find the common left node , Right node 
	Node *root=new Node;
	root->val=pre[preL];
	int k;
	int preVal=pre[preL+1];
	for(k=postL;k<=postR;k++){
    
		if(post[k]==preVal){
    
			break;
		}
	} 
	int left_num=k-postL+1;
	root->left=build(preL+1,preL+left_num,postL,postL+left_num-1);
	root->right=build(preL+left_num+1,preR,postL+left_num,postR-1);
	return root;
}

bool ok=false;
vector<int>in;
void inTravel(Node*root){
    
	if(root==NULL){
    
		return ;
	}
	inTravel(root->left);
	in.push_back(root->val);
	inTravel(root->right);
}
int main(){
    
	scanf("%d",&N);
	pre.resize(N);
	post.resize(N);
	for(int i=0;i<N;i++){
    
		scanf("%d",&pre[i]);
	}
	for(int i=0;i<N;i++){
    
		scanf("%d",&post[i]);
	}
	Node *root=build(0,N-1,0,N-1);
	// Print the results  
	if(!flag){
    
		printf("No\n");
	}else{
    
		printf("Yes\n");
	}
	inTravel(root);
	for(int i=0;i<in.size();i++){
    
		if(i)printf(" ");
		printf("%d",in[i]);
	}
	printf("\n");
	return 0;
}

2.4 Fourth question ： 1123 Is It a Complete AVL Tree (30 branch )

【 Subject portal 】

Binary balance tree ： To tell the truth, I haven't seen the template for a long time and forgot all of it ~

Here's a look 《 Algorithm notes 》 A little bit of memory found , It is absolutely necessary to look at the knowledge points before the exam （ In case you get , Basically, it's hard to push it out immediately ┗|｀O′|┛ Ow ~~）

  • Perfect binary tree ： The penultimate level of independent judgment , Other layers （ Except for the penultimate floor ） It must be full
  • AVL Trees 
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int>nodes;
struct Node{
    
	int val;
	int height=1;
	Node*left=NULL;
	Node*right=NULL;
};
int getHeight(Node*root){
    
	if(root==NULL){
    
		return 0;
	}else{
    
		return root->height;
	}
}
int getBalanceFactor(Node*root){
    
	return getHeight(root->left)-getHeight(root->right);
} 
void updateHeight(Node* &root){
    
	root->height=max(getHeight(root->left),getHeight(root->right))+1;
}
void L(Node* &root){
    
	Node *temp=root->right;
	root->right=temp->left;
	temp->left=root;
	updateHeight(root);
	updateHeight(temp);
	root=temp;
}
void R(Node* &root){
    
	Node *temp=root->left;
	root->left=temp->right;
	temp->right=root;
	updateHeight(root);
	updateHeight(temp);
	root=temp;
}
void build(Node* &root,int val){
    
	if(root==NULL){
    
		root=new Node;
		root->val=val;	
	}else{
    
		if(val<root->val){
    // Insert into the left subtree  
			build(root->left,val);
			updateHeight(root);// Update the height of the root node in the inner tree 
			if(getBalanceFactor(root)==2){
    
				// On the left 
				if(getBalanceFactor(root->left)==1){
    //LL
					R(root); 
				}else if(getBalanceFactor(root->left)==-1){
    //LR shape 
					L(root->left);
					R(root);
				} 
			}
		}else{
    
			build(root->right,val);
			updateHeight(root);// Update the height of the root node in the inner tree 
			if(getBalanceFactor(root)==-2){
    
				// On the right 
				if(getBalanceFactor(root->right)==-1){
    //RR
					L(root); 
				}else if(getBalanceFactor(root->right)==1){
    //RL shape 
					R(root->right);
					L(root); 
				}  
			}
		} 
	}
	return ;
}
// Level traversal 
bool flag=true;
int max_level=-1;
void levelTravel(Node*root){
    
	// The hierarchy traverses the last layer , want  
	queue<Node*>q;
	root->height=1;
	q.push(root);
	bool ok=false;
	while(!q.empty()){
    
		Node*top=q.front();
		max_level=max(max_level,top->height);
		q.pop();
		Node *temp; 
		
		if(top->left!=NULL){
    
			temp=top->left;
			temp->height=top->height+1;
			q.push(temp);
		}
		if(!ok){
    
			ok=true;
		}else{
    
			printf(" ");
		}
		printf("%d",top->val);
		if(top->right!=NULL){
    
			temp=top->right;
			temp->height=top->height+1;
			q.push(temp);
		}
	}
	return ;
} 
void check(Node*root){
    
	queue<Node*>q;
	root->height=1;
	q.push(root);
	bool ok=false;
	int nu=0;
	while(!q.empty()){
    
		Node*top=q.front();
		max_level=max(max_level,top->height);
		q.pop();
		Node *temp; 
		
		if(top->left!=NULL){
    
			temp=top->left;
			q.push(temp);
		}
		if(top->right!=NULL){
    
			temp=top->right;
			q.push(temp);
		}
		// Judge 
		if(top->left==NULL&&top->right!=NULL){
    
			flag=false;
		}
		if(top->height<max_level-1&&(top->left==NULL||top->right==NULL)){
    
			flag=false;
		}else if(top->height==max_level-1){
    
			if(!nu&&(top->left==NULL||top->right==NULL)){
    
				nu=1;
			}else if(nu&&(top->left!=NULL||top->right!=NULL)){
    
				flag=false;
			}
			
		}
		
	}
	return ;
}
int main(){
    
	scanf("%d",&N);
	nodes.resize(N);
	for(int i=0;i<N;i++){
    
		scanf("%d",&nodes[i]);
	}
	Node *root=NULL;
	for(int i=0;i<N;i++){
    
		build(root,nodes[i]);
	}
	// Output the answer  
	levelTravel(root);
	printf("\n");
	check(root);
	// contrast 
	if(flag){
    
		printf("YES\n");
	}else{
    
		printf("NO\n");
	}
	return 0;
}

3. Reference material

  1. C++ How to judge map Of key Whether the value exists

  2. 《 Algorithm notes 》AVL Trees part

原网站

版权声明
本文为[Republic cake]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202180554062066.html

边栏推荐

猜你喜欢

随机推荐