USTC机试_09

2021-01-12

1.处理：比如输入4，转化为16位二进制数 0000 0000 0000 0100，4个一组，相异或，变为0001，然后把0001转化为十进制的1输出

// 1.cpp : Defines the entry point for the console application.
//
#include<iostream>
#include<queue>
#include<math.h>
using namespace std;
queue<int> q;
int main()
{
    int x;
    cin>>x;
    while(x!=0){
        int a,b;
        a=x%2;//当前最后一位
        x/=2;
        b=x%2;
        a=a^b;//1 2位异或
        x/=2;
        b=x%2;
        a=a^b;//1 2 3位异或
        x/=2;
        b=x%2;
        a=a^b;//1 2 3 4位异或
        q.push(a);
    }
    int i=0,answer=0;
    while(!q.empty()){
        answer+=q.front()*pow(2,i++);
        q.pop();
    }
    cout<<answer<<endl;
}

2.将n个数由小到大排序，如果 n是奇数，输出正中间的数；如果n是偶数，输出
正中间的两个数

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1000;
int arr[MAXN];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    sort(arr,arr+n);
    if(n%2==0){
        cout<<arr[n/2-1]<<" "<<arr[n/2];
    }
    else cout<<arr[n/2];
}

3.文件读入类ABC00DE00…的二叉树先序序列，0表示叶子
输出：中序输出深度<=depth/2的节点，其中depth是你所建立的树的深度

#include<iostream>
#include<fstream>
using namespace std;
//数据:ABC00D00E00
int depth=0;
string pre;
int i=0;
struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data){}
};

TreeNode* buildTree(){//仅用带null符号的先序序列构建树
    if(i>pre.size()-1) return NULL;
    char c=pre[i++];
    if(c=='0') return NULL;
    TreeNode* T=new TreeNode(c);
    T->left=buildTree();
    T->right=buildTree();
    return T;
}

void PostOrder(TreeNode* T,int deep){//计算深度
    if(T==NULL)return ;
    if(deep>depth) depth=deep;
    PostOrder(T->left,deep+1);
    PostOrder(T->right,deep+1);
}

void PostOrder1(TreeNode* T,int deep){
    if(T==NULL)return ;
    if(deep>depth) depth=deep;
    PostOrder(T->left,deep+1);
    PostOrder(T->right,deep+1);
    if(deep<=depth/2){
        cout<<T->data;
    }
    return ;
}

int main(){
    ifstream infile("in.txt");
    getline(infile,pre);
    infile.close();
    cout<<pre<<endl;
    TreeNode* root=buildTree();
    PostOrder(root,1);
    //cout<<"deep:"<<depth<<endl;
    PostOrder1(root,1);
}