[PAT] 模板整理

梦里梦外; 2021-11-01 23:44 275阅读 0赞

1.并查集

int find(int x){
        if(x==fa[x]) return x;
        return fa[x]=find(fa[x]);
    }

int fa[MAX];
    int find(int x)
    {
    	int r=x,i=x,j;
    	while(fa[r]!=r)
    	r=fa[r];
    	while(fa[i]!=i)
    	j=fa[i],fa[i]=r,i=j;
    	return r;
    }
    void combine(int x,int y)
    {
    	int xx=find(x);
    	int yy=find(y);
    	if(xx<yy)
    	fa[yy]=xx;
    	else
    	fa[xx]=yy;
    }

2.dijstra最短路

int ma[MAX][MAX];
    memset(ma,INF,sizeof ma);
    memset(dis,INF,sizeof dis);
    memset(vis,0,sizeof vis);
    memset(pre,-1,sizeof pre);//前驱 
    memset(cost,INF,sizeof cost);//花费 
    dis[s]=0;
    for(i=0;i<n;i++)
    {
    	int d=INF;
    	for(j=0;j<n;j++)
    	{
    		if(vis[j]==0&&dis[j]<d)
    		{
    			d=dis[j];
    			next=j;
    		}
    	}
    	vis[next]=1;
    	for(j=0;j<n;j++)
    	{
    		if(dis[j]>dis[next]+ma[next][j])
    		{
    			dis[j]=dis[next]+ma[next][j];
    			sum[j]=sum[next]+cost[next][j];
    			pre[j]=next;
    		}
    		else if(dis[j]==dis[next]+ma[next][j])
    		{
    			if(sum[j]>sum[next]+cost[next][j])
    			{
    				sum[j]=sum[next]+cost[next][j];
    				pre[j]=next;
    			}
    		}
    	}
    }

3.BST 建树-算层数

int ans[1005];//每层节点数
    int maxl;//深度
    struct node
    {
    	int val;
    	struct node *l,*r;
    	node()
    	{
    		val=-10005;
    		l=r=NULL;
    	}
    };
    void insert(struct node* root,int k,int level)
    {
    	if(root->val==-10005)
    	{
    		root->val=k;
    		if(level>maxl)
    		maxl=level;
    		ans[level]++;
    		return;
    	}
    	if(k<=root->val)
    	{
    		if(root->l==NULL)
    		root->l=new node;
    		insert(root->l,k,level+1);
    	}	
    	else
    	{
    		if(root->r==NULL)
    		root->r=new node;
    		insert(root->r,k,level+1);
    	}
    }
    int main()
    {
    	int n,i,j,k;
    	node *root=new node;
    	memset(ans,0,sizeof ans);
    	maxl=-1;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&k);
    		insert(root,k,1);
    	}
    	//printf("%d\n",maxl);
    	printf("%d + %d = %d\n",ans[maxl],ans[maxl-1],ans[maxl]+ans[maxl-1]);
    }

4.BST的中序遍历=从小到大顺序输出：还原一棵树

struct Node
    {
    	int val;
    	int l,r;
    }tree[105];
    
    int a[105],p;
    void Inorder(int x)
    {//中序遍历建立BST 
    	if(tree[x].l!=-1) Inorder(tree[x].l);
    	tree[x].val=a[p++];
    	if(tree[x].r!=-1) Inorder(tree[x].r);
    }
    int main()
    {
    	int n,i,j;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	scanf("%d%d",&tree[i].l,&tree[i].r);
    	for(i=0;i<n;i++)
    	scanf("%d",&a[i]);
    	sort(a,a+n);
    	p=0;
    	Inorder(0);
    }

5.二叉树的层次遍历

vector<int> v;
    queue<Node> q;
    q.push(tree[0]);
    while(!q.empty())
    {
    	Node u=q.front();
    	q.pop();
    	v.push_back(u.val);
    	if(u.l!=-1)
    	q.push(tree[u.l]);
    	if(u.r!=-1)
    	q.push(tree[u.r]);
    }
    for(i=0;i<v.size()-1;i++)
    printf("%d ",v[i]);
    printf("%d\n",v[v.size()-1]);

6.AVL建立+层次遍历输出 T123

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    struct node
    {
    	int val;
    	node *l,*r; 
    };
    int height(node *root)
    {
    	if(root==NULL)	return 0;
    	return max(height(root->l),height(root->r))+1;
    }
    node *right(node *root)
    {
    	node *t=root->l;
    	root->l=t->r;
    	t->r=root;
    	return t;
    }
    node *left(node *root)
    {
    	node *t=root->r;
    	root->r=t->l;
    	t->l=root;
    	return t;
    }
    node *rightleft(node *root)
    {
    	root->r=right(root->r);
    	return left(root);
    }
    node *leftright(node *root)
    {
    	root->l=left(root->l);
    	return right(root);
    }
    node *insert(node *root,int x)
    {
    	if(root==NULL)
    	{
    		root=new node();
    		root->val=x;
    		root->l=root->r=NULL;
    	}
    	else if(x<root->val)
    	{
    		root->l=insert(root->l,x);
    		if(height(root->l)-height(root->r)==2)
    		root= x<root->l->val ?right(root):leftright(root);
    		
    	}
    	else
    	{
    		root->r=insert(root->r,x);
    		if(height(root->l)-height(root->r)==-2)
    		root= x>root->r->val ?left(root):rightleft(root);
    		
    	}
    	return root;
    }
    int a[50];
    void dfs(node *root,int p)
    {
    	if(root==NULL) return;
    	a[p]=root->val;
    	dfs(root->l,2*p+1);
    	dfs(root->r,2*p+2);
    }
    int main()
    {
    	int n,i,x;
    	node *root=NULL;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&x);
    		root=insert(root,x);
    	}
    	memset(a,-1,sizeof a);
    	dfs(root,0);
    	int flag=0;
    	int j=1;
    	printf("%d",a[0]);
    	for(i=1;i<n;i++)
    	{
    		while(a[j]==-1)
    		{
    			flag=1;
    			j++;
    		}
    		printf(" %d",a[j++]);
    	}
    	if(flag) printf("\nNO\n");
    	else printf("\nYES\n");
    }

7.字符串处理

截取：string s=ss.substr(a,b) 从a截取到b，ss.substr(a) 从a截取到最后一位

字符串转数字：  
atoi（将字符串转换成整型数）  
atof（将字符串转换成浮点型数）

sscanf和sprintf的用法：[https://blog.csdn.net/TheWise\_lzy/article/details/100182865][https_blog.csdn.net_TheWise_lzy_article_details_100182865]

[https_blog.csdn.net_TheWise_lzy_article_details_100182865]: https://blog.csdn.net/TheWise_lzy/article/details/100182865