复试上机真题历年回顾-2019

字符串解析

将字符串看成不同的字符切片,切片不可重复.
按字母序输出所有切片,每个切片一行.

样例

输入
aaabbcaaabaa
输出
aa
aaa
b
bb
c

遍历就行 注意当前切片之前是否出现过

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define int long long 
#define endl '\n'
signed main(){
    string str;
    cin>>str;
    map<string,int>mp;//记录切片出现的次数
    for(int i=0;str[i];i++){
        int j =i;
        while(j<str.length()&&str[j]==str[i]) j++;
        string tmp =str.substr(i,j-i);//切片长度为j-i
        mp[tmp]++;
        if(j==str.size()) break;
        i=j-1;//回退一步
    }
    for(auto t:mp) {
        cout<<t.fi<<endl;//输出切片
        }
}

求哈夫曼树的最短路径

懒得放题目了 就是考察优先队列 

大根堆写法

priority_queue<int>q

小根堆写法*

priority_queue<int,vector<int>,greater<int>>q

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define x first
#define y second

signed main(){
    int n;
    cin>>n;
    priority_queue<int,vector<int>,greater<int>>q;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        q.push(x);
    }
    int res=0;
    while(q.size()>1){
        int a=q.top();
        q.pop();
        int b=q.top();
        q.pop();
        res=res+a+b;//记录分支节点的权值
        q.push(a+b);
    }

   cout<<res<<endl;
    return 0;
}