4月26日快手工程C笔试题解

第一题大概意思是每个域名下面有一定的路径,如果两个域名下的请求路径完全相同,那么就把两个域名视为相同的,最后输出有多少组相同的就可以。
既然是集合第一时间想到的是STL的set,STL里面set已经重载了小于号,可以很轻易的判断是否相等。
把每个请求分成地址和路径,然后把路径存到地址对应的集合里面,为了比较方便,把路径做了哈希。
直接暴力比较会超时,所以按照路径集合作为关键字,来一个排序就行。
我用的是multimap,用其他容器也可以,接下来处理就是相当自然的了。
注意的是"http://xxx.yyy"和"http://xxx.yyy/"是不同的。
#include <algorithm>
#include <iostream>

#include <vector>
#include <string>
#include <queue>
#include <stack>

#include <sstream>

#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ui64=unsigned long long;

int main(){
    int N;
    cin >> N;
    string domain,route;
    unordered_map<string,size_t> routeID;
    int idCount=0;
    // 每个域名包含的路径集合
    unordered_map<string,set<int>> contains;
    for(int i=0;i<N;i++){
        string url;
        cin >> url;
        domain="http://";
        route="";
        int j=7;
        for(;url[j]!='/' && j<url.length();j++){ domain.push_back(url[j]); }
        for(;j<url.length();j++){ route.push_back(url[j]); }
        int id;
        if(routeID.count(route)){
            id=routeID[route];
        } else {
            id=idCount++;
            routeID[route]=id;
        }
        contains[domain].insert(id);
    }
    // 按照集合作为关键字排序
    multimap<set<int>,string> sorts;
    for(auto pos:contains){
        sorts.insert({pos.second,pos.first});
    }
    // 判断有没有相等的集合
    unordered_map<string,vector<string>> results;
    auto pos=sorts.begin();
    while(pos!=sorts.end()){
        auto next=pos;
        next++;
        while(next!=sorts.end() && !(pos->first<next->first)){
            results[pos->second].push_back(next->second);
            next++;
        }
        pos=next;
    }
    // 输出
    cout << results.size() << endl;
    for(auto pos=results.begin();pos!=results.end();pos++){
        cout << pos->first;
        for(auto str:pos->second){
            cout << " " << str;
        }
        cout << endl;
    }
    return 0;
}

第二题其实可以反过来看,和城市i相连的城市只有i/2,i*2和i*2+1,所以从u到v的路径应该是先从u向1走,走到合适的拐点再从这个拐点向v走。
把这个国家的所有路径想象成一颗巨大的二叉树就行。路线应该是从起点先向根节点,然后到最低的共同祖先,再向终点前进
求路径的时间是O(lnN),所以把所有增加过过路费的路径存在哈希表里面就可以。
#include <algorithm>
#include <iostream>

#include <vector>
#include <string>
#include <queue>
#include <stack>

#include <sstream>

#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ui64=unsigned long long;

// 求路径
unordered_set<ui64> getRoute(ui64 u,ui64 v){
    unordered_set<ui64> route;
    ui64 temp=u;
    while(temp>0){
        route.insert(temp);
        temp>>=1;
    }
    temp=v;
    while(temp>0){
        if(!route.count(temp)){
            route.insert(temp);
        } else {
            route.erase(temp);
        }
        temp>>=1;
    }
    return route;
}

int main(){
    // cost[i]表示从i/2走到i要花的路费
    unordered_map<ui64,ui64> cost;
    int n;
    cin >> n;
    int command;
    ui64 u,v,w;
    for(int i=0;i<n;i++){
        cin >> command >> u >> v;
        unordered_set<ui64> route=getRoute(u,v);
        if(command==1){
            cin >> w;
            for(auto r:route){
                cost[r]+=w;
            }
        } else {
            ui64 total=0;
            for(auto r:route){
                total+=cost.count(r)?cost[r]:0;
            }
            cout << total << endl;
        }
    }
    return 0;
}

第三题直接手动构造就可以:
AAAAAAAAAAAAAA
ABABABABABABAB
AABABABABABABA
AAAAAAAAAAAAAA
用一定数量的A把其他花分隔开,同时保证分割其他花的A仍然被视为是一组
类似这样的思路,最后多出来的A用B来分割就可以
在全为100的情况下也没有超过50*50的限制
#include <algorithm>
#include <iostream>

#include <vector>
#include <string>
#include <queue>
#include <stack>

#include <sstream>

#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ui64=unsigned long long;

int main(){
    int flowers[4];
    for(int i=0;i<4;i++){
        cin >> flowers[i];
    }
    string row;
    vector<string> grid;
    flowers[0]--;flowers[1]--;
    for(int i=1;i<4;i++){
        if(flowers[i]==0){
            continue;
        }
        int r=0;
        while(flowers[i]>0){
            row=string(50,'A');
            if(!(r&1)) grid.push_back(row);
            for(int j=1+(r&1);j<50 && flowers[i]>0;j+=2){
                row[j]='A'+i;
                flowers[i]--;
            }
            grid.push_back(row);
            r++;
        }
    }
    grid.push_back(string(50,'A'));
    if(flowers[0]!=0){
        int r=0;
        while(flowers[0]>0){
            row=string(50,'B');
            if(!(r&1)) grid.push_back(row);
            for(int j=1+(r&1);j<50 && flowers[0]>0;j+=2){
                row[j]='A';
                flowers[0]--;
            }
            grid.push_back(row);
            r++;
        }
    }
    grid.push_back(string(50,'B'));
    cout << grid.size() << " " << 50 << endl;
    for(auto row:grid){
        cout << row << endl;
    }    
    return 0;
}

#include <algorithm>
#include <iostream>

#include <vector>
#include <string>
#include <queue>
#include <stack>

#include <sstream>

#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ui64=unsigned long long;

vector<size_t> father;
size_t getFather(int x){
    if(father[x]==x) return father[x];
    father[x]=getFather(father[x]);
    return father[x];
}
void setFather(int x,int y){
    int xFather = getFather(x);
    int yFather = getFather(y);
    father[xFather] = yFather;
    return;
}

int main(){
    int X,Y;
    cin >> X >> Y;
    if(X==0 || Y==0){
        cout << 0 << endl;
        return 0;
    }
    vector<vector<int>> grid(X,vector<int>(Y));
    for(int x=0;x<X;x++){
        for(int y=0;y<Y;y++){
            cin >> grid[x][y];
        }
    }
    father.resize(X*Y+1);
    for(size_t num=0;num<father.size();num++){
        father[num]=num;
    }
    for(int x=0;x<X;x++){
        for(int y=0;y<Y;y++){
            if(grid[x][y]==0){
                father[x*Y+y+1]=0;
            } else if (x==0 || x==X-1 || y==0 || y==Y-1){
                setFather(x*Y+y+1,0);
            } else {
                if(grid[x-1][y]==1) setFather((x-1)*Y+y+1,x*Y+y+1);
                if(grid[x+1][y]==1) setFather((x+1)*Y+y+1,x*Y+y+1);
                if(grid[x][y-1]==1) setFather(x*Y+y,x*Y+y+1);
                if(grid[x][y+1]==1) setFather(x*Y+y+2,x*Y+y+1);
            }
        }
    }
    int count=0;
    for(int i=0;i<=X*Y;i++){
        if(getFather(i)==i){
            count++;
        }
    }
    cout << count-1 << endl;
    return 0;
}


#快手2020春招##快手##笔试题目#
全部评论
😔求问第二题和第三题解题思路
点赞 回复
分享
发布于 2020-04-26 18:05
大佬,还有其他题分享吗
点赞 回复
分享
发布于 2020-04-26 18:05
淘天集团
校招火热招聘中
官网直投
第一题就是一个卡特兰数。。。。。。。。3分钟就过了
点赞 回复
分享
发布于 2020-04-26 18:08
可能题目不一样,我最开始没说清楚。
点赞 回复
分享
发布于 2020-04-26 18:14
给大佬顶个贴
点赞 回复
分享
发布于 2020-04-26 18:44
MARK
点赞 回复
分享
发布于 2020-04-26 19:39
请问26号是最后一场笔试了吗?
点赞 回复
分享
发布于 2020-04-27 02:21
自大了,倒着写,结果没写完A题,出来就扇了自己一巴掌
点赞 回复
分享
发布于 2020-04-27 11:17

相关推荐

15 19 评论
分享
牛客网
牛客企业服务