笔试编程题0414

前言

2019搜狐春招笔试题，两道都ac了，还是挺开心的。

题目

系统设计

会员成长值 = 每天成长值 + 任务成长值。

大体意思是：给定多行，每行第一个值为1给出了某个时间范围每天的成长值，每行第一个值为2给出了某天做任务的任务值。每行中每天的成长值的时间范围可能有重复的，选择成长值最大的来作为当天最大成长值。求出总的会员成长值。

3 
1 1 5 10
2 3 4
1 4 6 -5
输出49

思路：遍历找出每天成长值的时间范围，然后依次比较每天的成长值，得到最大的成长值作为当天的成长值。

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int N;
    cin>>N;
    int len = N;
    vector<vector<int>> growVec;
    vector<vector<int>> tastVec;
    int num;
    while(len--){
        cin>>num;
        if(num == 1){   //成长
            int tem;
            vector<int> ivec;
            for(int i=0;i<3;++i){
                cin>>tem;
                ivec.push_back(tem);
            }
            growVec.push_back(ivec);
        }else{   //任务
            int tem;
            vector<int> ivec;
            for(int i=0;i<2;++i){
                cin>>tem;
                ivec.push_back(tem);
            }
            tastVec.push_back(ivec);
        }
    }
    /*
    for(auto ivec : growVec){
        for(auto ele : ivec) cout<<ele<<" ";
        cout<<endl;
    }
    for(auto ivec : tastVec){
        for(auto ele : ivec) cout<<ele<<" ";
        cout<<endl;
    }
    cout<<"-------------------"<<endl;
    */
    int mintime = 1000000;
    int maxtime = -1000000;
    for(auto iter = growVec.begin();iter!=growVec.end();++iter){
        if((*iter)[0] < mintime) mintime = (*iter)[0];
        if((*iter)[1] > maxtime) maxtime = (*iter)[1];
    }
    //cout<<mintime<<" "<<maxtime<<endl;   //时间范围
    int res = 0;
    for(int i = mintime;i<=maxtime;++i){
        int MaxValue = -1000000;
        for(auto iter = growVec.begin();iter!=growVec.end();++iter){
            if(i>=(*iter)[0]&&i<=(*iter)[1]){
                if(MaxValue<(*iter)[2]) MaxValue = (*iter)[2];
            }
        }
        //cout<<MaxValue<<endl;
        res += MaxValue;
    }
    //cout<<"here"<<endl;
    for(auto iter = tastVec.begin();iter!=tastVec.end();++iter){
        res += (*iter)[1];
    }
    if(res < 0) cout<<<<endl;
    cout<<res<<endl;
    return 0;
}

Top K问题

找出某个序列中第K小的数。

思路：维护一个K大的大根堆，堆顶元素是最大的值，遍历数组序列，如果存在比堆顶元素小的数，将堆顶元素删除，将新值添加进堆。

注：默认所有make_heap操作都是大根堆，也就是所有的第三个参数时less(),如果需要生成小根堆，操作也是一样的，第三个参数全为greater()。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> GetSmallKNum(vector<int> &input, int k) {
    vector<int> ivec;
    if(k>input.size() || k<1) return ivec;
    auto iter = input.begin();  //从第一个元素开始遍历
    for(int i=0;i<k;++i){
        ivec.push_back(*iter);
        ++iter;
    }
    make_heap(ivec.begin(),ivec.end());
    auto end = input.end();
    for(;iter!=end;++iter){
        if(*iter<ivec[0]){  //小于最大值
            pop_heap(ivec.begin(),ivec.end());  //删除堆顶元素
            ivec.pop_back();
            ivec.push_back(*iter);
            push_heap(ivec.begin(),ivec.end());  //插入新的元素
        }
    }
    //对大根堆进行排序
    sort_heap(ivec.begin(),ivec.end());
    return ivec;
};


int main()
{
    int len,k;
    cin>>len>>k;
    int size = len;
    vector<int> input;
    int num;
    while(len--){
        cin>>num;
        input.push_back(num);
    }
    vector<int> res = GetSmallKNum(input,k);
    int length = res.size();
    int i;
    for(i=0;i<length-1;++i) cout<<res[i]<<",";
    cout<<res[i]<<endl;
    return 0;
}