机试常见模板

说明：

常见的如树的层次遍历、中序遍历、前序遍历、后序遍历以及根据前/后+中序遍历推导出二叉树的结构的题目本次未整理；

Dijkstra+DFS准备单独整理一下

并查集也可以单独整一下

---

以下仅整理出题较少但是套路性很强的模板题：

• AVL树
• 完全二叉树判断
• 排序过程
• 二次探查解决冲突的哈希表

• 机试常见模板
  • 1. 树
    • 1.1 AVL树
    • 1.2 判断是否是完全二叉树
  • 2. 排序
    • 2.1 插入排序
    • 2.2 堆排序
    • 2.3 归并排序
  • 3. 哈希表二次探查

1. 树

1.1 AVL树

AVL二叉平衡树个人感觉考频中下，但是属于必背模板~

涉及题目：

构建AVL模板：

#include<bits/stdc++.h>
using namespace std;
//构建AVL树模板
int N;
vector<int>v; 
//AVL树相关函数 
struct Node{
	int val;
	int height;
	Node*left=NULL;
	Node*right=NULL;
};
Node*root=NULL;
Node*newNode(int val){
	Node*node=new Node;
	node->val=val;
	node->height=1;
	return node;
}
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=newNode(val);
	}else if(val< root->val){
		build(root->left,val);
		UpdateHeight(root);
		if(getBalanceFactor(root)==2){
			if(getBalanceFactor(root->left)==1){
				//LL
				R(root);
			}else if(getBalanceFactor(root->left)==-1){
				//LR
				L(root->left);
				R(root);
			}
		}
	}else{
		build(root->right,val);
		UpdateHeight(root);
		if(getBalanceFactor(root)==-2){
			if(getBalanceFactor(root->right)==-1){
				//RR
				L(root);
			}else if(getBalanceFactor(root->right)==1){
				//RL
				R(root->right);
				L(root);
			}
		}
	}
}
int main(){
	scanf("%d",&N);
	v.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&v[i]);
	}
	for(int i=0;i<N;i++){
		build(root,v[i]);//root代表AVL树的根节点，build就是将val不断插入到以root为根节点的AVL树中再更新的过程
	}
	return 0;
} 

1.2 判断是否是完全二叉树

isCBT模板：

//判断是否是完全二叉树
bool isCBT(Node*root){
	queue<Node*>q;
	q.push(root);
	while(!q.empty()){
		Node*top=q.front();
		if(top==NULL){
			break;
		}
		q.pop();
		q.push(top->left);
		q.push(top->right);
	}
	while(!q.empty()){
		Node*top=q.front();
		if(top!=NULL){
			return false;
		}
		q.pop();
	}
	return true;
} 

2. 排序

排序过程题其实面试中问的比较多，实际编程我们习惯写sort去解决，但是PAT偶尔也会让选手进行手撕。

考到的话基本上还是能写出来的，模板不是一定要背~但是一些特殊的比如堆排序、快速排序还是记一下比较好（防止考到一脸win号）

这边列出考过的几个排序的模板。

涉及题目：

2.1 插入排序

代码模板：

判断是否是插入排序过程中产生序列，并输出此序列的下一个序列

bool insertSort(){
	bool flag=false;
	temp=v0;
	for(int i=1;i<N;i++){
		if(temp==v1){
			flag=true;
		}
		int pos=i;
		int val=temp[i];
		while(pos){
			if(temp[pos-1]>val){
				swap(temp[pos],temp[pos-1]);
			}else{
				break;
			}
			pos--;
		}
		temp[pos]=val;
		if(flag){
			return flag;
		}
	}
	return flag;
}

2.2 堆排序

代码模板：

判断是否是堆排序中产生的序列并且输出此序列的下一个序列：

void Adjust(vector<int>&v,int len,int index){
	int left=index*2+1;
	int right=index*2+2;
	int max_index=index;
	if(left<len&&v[left]>v[max_index])max_index=left;
	if(right<len&&v[right]>v[max_index])max_index=right;
	if(max_index!=index){
		swap(v[index],v[max_index]);
		Adjust(v,len,max_index);
	}
} 
bool heapSort(){
	temp=v0;
	bool flag=false;
	//初始化 
	for(int i=(N-1)>>1;i>=0;i--){
		Adjust(temp,N,i);
	}
	for(int i=N-1;i>=1;i--){
		if(temp==v1){
			flag=true;
		}
		swap(temp[0],temp[i]);
		Adjust(temp,i,0);
		if(flag){
			break;
		} 
	}
	return flag;
}

完整的堆排序代码：

#include<bits/stdc++.h>
using namespace std;
//0 1 2 3 4 
void Adjust(vector<int> &v,int len,int index){
	int left=((index+1)<<1)-1;
	int right=(index+1)<<1;
	int max_index=index;
	if(left<len&&v[max_index]<v[left])max_index=left;
	if(right<len&&v[max_index]<v[right])max_index=right;
	if(max_index!=index){
		swap(v[max_index],v[index]);
		Adjust(v,len,max_index);
	}
}
void heapSort(vector<int> &v,int len){
	for(int i=((len)>>1)-1;i>=0;i--){
		Adjust(v,len,i);
	}
	for(int i=len-1;i>=1;i--){
		swap(v[0],v[i]);
		Adjust(v,i,0);
	}
}
int N;
int main(){
	scanf("%d",&N);
	vector<int>v(N);
	for(int i=0;i<N;i++){
		scanf("%d",&v[i]);
	}
	heapSort(v,N);
	printf("排序后：");
	/* 
	10
	8 9 7 2 3 1 2 3 3 0
	*/
	for(int i=0;i<N;i++){
		printf("%d ",v[i]);
	}
	return 0;
} 

2.3 归并排序

代码模板：

判断是否是归并排序中产生的序列并且输出此序列的下一个序列：

bool mergeSort(){
	temp=v0;
	bool flag=false;
	int block=1;
	while(block<=N){
		if(temp==v1){
			flag=true;
		}
		int i;
		for(i=0;i<N/block;i++){
			if((i+1)*block<=N){
				sort(temp.begin()+i*block,temp.begin()+(i+1)*block);
			}
		}
		if(N%block){
			sort(temp.begin()+i*block,temp.end());
		}
		if(flag){
			return flag;
		}
		block*=2;
	} 
	return flag;
}

3. 哈希表二次探查

主要是二次探查的界限在于哈希表本身的大小

例题：【1078 Hashing】

代码：

#include<bits/stdc++.h>
using namespace std;
int MSize,N,temp;
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;
}
vector<int>table;
int Hash(int x){
	int pos=-1;
	for(int i=0;i<=MSize;i++){
		int tpos=(i*i+x)%MSize;
		if(table[tpos]==-1){
			pos=tpos;
			break;
		}
	}
	return pos;
}
int main(){
	scanf("%d%d",&MSize,&N);
	while(!isPrime(MSize)){
		MSize++;
	}
	table.resize(MSize,-1);
	for(int i=0;i<N;i++){
		scanf("%d",&temp);
		//hash查找位置
		int pos=Hash(temp);
		if(i){
			printf(" ");
		}
		if(pos==-1){
			printf("-");
		}else{
			table[pos]=temp;
			printf("%d",pos);
		}
	}
	return 0;
}