USTC机试_07上

1.编写程序，判断回文数

#include<iostream>


using namespace std;

int Reverse(int x){
    int result=0;
    while(x!=0){
        result=result*10+x%10;
        x/=10;
    }
    return result;
}

int main(){
    int n;
    while(cin>>n){
        if(Reverse(n)==n) cout<<"Y"<<endl;
        else cout<<"N"<<endl;
    }
}

2.队列的循环报数问题

#include<iostream>
#include<queue>

using namespace std;

int main(){
    int n;
    cin>>n;
    queue<int> q;o
    for(int i=1;i<=n;i++) q.push(i);
    while(!q.empty()){
        cout<<q.front()<<" ";//报号1
        q.pop();
        if(!q.empty()){
            q.push(q.front());//报号2
            q.pop();
        }
    }
}

3.图的最小生成树

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=1001;
struct Edge{
    int from;
    int to;
    int length;
    bool operator< (const Edge& e) const{
        return length<e.length;
    }
};

Edge edge[MAXN*MAXN];
int father[MAXN];
int height[MAXN];
void Initial(int n){
    for(int i=0;i<n;i++){
        father[i]=i;
        height[i]=0;
    }
}

int Find(int x){
    if(x!=father[x]) father[x]=Find(father[x]);
    return father[x];
}

void Union(int x,int y){
    x=Find(x);
    y=Find(y);
    if(x!=y){
        if(height[x]<height[y]) father[x]=y;
        else if(height[y]<height[x]) father[y]=x;
        else{
            father[y]=x;
            height[x]++;
        }
    }
    return ;
}

int kruskal(int n,int edgeNumber){
    Initial(n);
    sort(edge,edge+edgeNumber);
    int sum=0;
    for(int i=0;i<edgeNumber;i++){
        Edge current=edge[i];
        //即from与to上溯的根结点不一样
        //也即加上edge[i]不会形成环
        if(Find(current.from)!=Find(current.to)){
            Union(current.from,current.to);
            sum+=current.length;
        }
    }
    return sum;
}

int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        //用于给了两两之间的距离修路的问题
        int edgeNumber=n*(n-1)/2;
        for(int i=0;i<edgeNumber;i++){
            cin>>edge[i].from>>edge[i].to>>edge[i].length;
        }
        int answer=kruskal(n,edgeNumber);
        cout<<answer<<endl;
    }
}

4.后序中序得先序

#include<iostream>
#include<cstring>
using namespace std;

struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data){}
};

string in;
string post;

TreeNode* postin(int l1,int h1,int l2,int h2){
    char data=post[h1];
    cout<<data<<endl;
    TreeNode* T=new TreeNode(data);
    int i;
    for(i=l2;data!=in[i];i++);//这里i的开头是l2
    int llen=i-l2;
    int rlen=h2-i;
    if(llen) T->left=postin(l1,l1+llen-1,l2,l2+llen-1);
    else T->left=NULL;
    if(rlen) T->right=postin(h1-rlen,h1-1,h2-rlen+1,h2);
    else T->right=NULL;
    return T;
}

void PreOrder(TreeNode* T){
    if(T==NULL) return;
    cout<<T->data;
    PreOrder(T->left);
    PreOrder(T->right);
}

int main(){
    cin>>post>>in;
    TreeNode* root=postin(0,post.size()-1,0,in.size()-1);
    PreOrder(root);
}

赏

谢谢你请我吃糖果