USTC机试_08下

2021-01-12

1.输入十进制正整数将其转换成任意的进制

#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
int main(){
    int n,m;
    cin>>n;
    cout<<"进制:";
    cin>>m;
    while(n!=0){
        v.push_back(n%m);
        n/=m;
    }
    for(int i=v.size()-1;i>=0;i--){
        cout<<v[i];
    }
}

2.从文件读入 2个矩阵，转置后相加再输出

#include<iostream>
#include<fstream>
#include<string>
#include<cstdlib>

using namespace std;
const int n=3;
const int m=2;
int matrix1[n][m];
int matrix2[n][m];
int main(){
    ifstream infile("in.txt");
    string s;
    for(int i=0;i<m;i++){
        getline(infile,s);
        for(int j=0;j<n;j++){
            if(s.find(" ")!=string::npos){
                int pos=s.find(" ");
                matrix1[j][i]=atoi((char*)s.substr(0,pos).data());//转置
                s=s.substr(pos+1);
            }
            else{
                matrix1[j][i]=atoi((char*)s.data());
            }
        }
    }
    for(int i=0;i<n;i++){
        getline(infile,s);
        for(int j=0;j<m;j++){
            if(s.find(" ")!=string::npos){
                int pos=s.find(" ");
                matrix2[i][j]=atoi((char*)s.substr(0,pos).data());
                s=s.substr(pos+1);
            }
            else{
                matrix2[i][j]=atoi((char*)s.data());
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<matrix1[i][j]+matrix2[i][j]<<" ";
        }
        cout<<endl;
    }
}

3.读入一个文件，第一行是字符串集合个数，第二行到第五行是这四个集合，从中
找到，字符串集合中出现两次的字符串，然后标识出第几个集合（行数）

#include<iostream>
#include<fstream>
#include<map>
#include<cstdlib>
#include<string>
using namespace std;
map<string,int> m;
void Count1(string key){
    if(m.find(key)==m.end()){//没找到这个key
        m.insert(pair<string,int>(key,1));
    }
    else{//已经存在这个key
        m[key]=m[key]+1;
    }
}

int main(){
    string s;
    ifstream infile("in.txt");
    getline(infile,s);
    int n=atoi((char*)s.data());

    for(int i=0;i<n;i++){
        getline(infile,s);
        while(s.size()>0){
            if(s.find(" ")!=string::npos){//
                int pos=s.find(" ");
                string key=s.substr(0,pos);
                Count1(key);
                s=s.substr(pos+1);
            }
            else{
                string key=s;
                Count1(key);
                s=s.substr(s.size());//为了能跳出循环
            }
        }
    }
    map<string,int>::iterator it;
    for(it=m.begin();it!=m.end();it++){//
        if(it->second==2){
            ifstream in("in.txt");
            string s; int i=0;
            getline(in,s);
            while(getline(in,s)){
                i++;
                if(s.find(it->first)!=string::npos){
                    cout<<it->first<<" "<<i; break;
                }
            }
            in.close();
            cout<<endl;
        }
    }

}

4.给一个先序(中序)遍历序列，按层次输出该树的结点

#include<iostream>
#include<queue>

using namespace std;

string pre;
string in;

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

void LevelOrder(TreeNode* T){
    queue<TreeNode*> q;
    q.push(T);
    while(!q.empty()){
        TreeNode* p=q.front();
        cout<<p->data;
        q.pop();
        if(p->left) q.push(p->left);
        if(p->right) q.push(p->right);
    }
    return ;
}


TreeNode* build(int l1,int h1,int l2,int h2){//前序中序建树
    char c=pre[l1];
    TreeNode* T=new TreeNode(c);
    int i;
    for(i=l2;in[i]!=c;i++) ;
    int llen=i-l2;
    int rlen=h2-i;
    if(llen) T->left=build(l1+1,l1+llen,l2,l2+llen-1);
    else T->left=NULL;
    if(rlen) T->right=build(h1-rlen+1,h1,h2-rlen+1,h2);
    else T->right=NULL;
    return T;
}

int main(){
    cin>>pre>>in;
    TreeNode* root=build(0,pre.size()-1,0,in.size()-1);
    LevelOrder(root);
}