快手笔试 1,2,4解析

楼主刚参加完快手笔试，做自闭了，最终AC 1,2,4。现在将代码po出来，希望能帮助大家。

第一题

1.对字符串解析。

2.提取域名作为key,地址作为value 构造map

3.根据2构造的map,反向构造map。

4.得到答案。

#include<bits/stdc++.h>
using namespace std;
map<string,set<string>>m;
map<set<string>,vector<string>>m2;
vector<string>alltop;
void process(string str){
    string top;
    int n=str.size();
    int div=-1;
    for(int i=7;i<n;i++){
        if(str[i]=='/'){
            div=i;
            break;
        }
        top+=str[i];
    }
    if(m.count(top)==0){
        alltop.push_back(top);
    }
    if(div==-1){
		m[top].insert("---");	
	}
	else if(div==n-1){
		m[top].insert("....");
	}
	else{
    	string name=str.substr(div+1,str.size()-div);
    	m[top].insert(name);
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string str;
        cin>>str;
        process(str);
    }
    int n=alltop.size();
    vector<vector<string>>res;
    for(auto p:m){
        m2[p.second].push_back(p.first);
    }
    for(auto p:m2){
    	if(p.second.size()>1){
    		res.push_back(p.second);
    	}
	}
	cout<<res.size()<<endl;
    for(int i=0;i<res.size();i++){
        for(int j=0;j<res[i].size()-1;j++){
            cout<<"http://"<<res[i][j]<<" ";
        }
        cout<<"http://"<<res[i].back();
        cout<<endl;
    }
    return 0;
}

2。

这个题是树的一个变种，考察递归的理解和使用。

主要是两个函数，一个是对树上的路径进行增加，一个是根据给定起点和终点求value.

#include<bits/stdc++.h>
using namespace std;
 map<pair<long long ,long long>,long long>m;//保存从i到j的的情况
void add(long long i,long long j,long long c){//路径增加
    if(i>j&&i==2*j){
        m[{j,i}]+=c;
        return;
    }
    else if(j>i&&j==2*i){
        m[{i,j}]+=c;
        return;
    }
    else if(j==i){return;}
    if(j>i){
        m[{j/2,j}]+=c;
        add(i,j/2,c);
    }
    else{
        m[{i/2,i}]+=c;
        add(i/2,j,c);
    }
}
void getSum(long long i,long long j,long long&res){//求值
     if(i>j&&i==2*j){
        res+=m[{j,i}];
        return;
    }
    else if(j>i&&j==2*i){
        res+=m[{i,j}];
        return;
    }
    if(j==i){return;}
    if(j>i){
        res+=m[{j/2,j}];
        getSum(i,j/2,res);
    }
    else if(j<i){
        res+=m[{i/2,i}];
        getSum(i/2,j,res);
    }
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int num;
        cin>>num;
        if(num==1){
            long long a,b,c;
            cin>>a;
            cin>>b;
            cin>>c;
            add(a,b,c);
        }
        else{
            long long a,b;
            cin>>a>>b;
            long long res=0;
            getSum(a,b,res);
            cout<<res<<endl;
        }
    }
    return 0;
}

4.简单的BFS

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>dir={{0,1},{1,0},{-1,0},{0,-1}};
void bfs(int i,int j,vector<vector<int>>&nums,int& res){
    queue<pair<int,int>>Q;
    Q.push({i,j});
    nums[i][j]=-1;
    int m=nums.size(),n=nums[0].size();
    bool sign=i==0||i==m-1||j==0||j==n-1;//表示是否被包围
    while(!Q.empty()){
        int s=Q.size(),idx=0;
        while(idx++<s){
            auto p=Q.front();
            Q.pop();
            for(auto d:dir){
                int x=p.first+d.first;
                int y=p.second+d.second;
                if(x>=0&&x<m&&y>=0&&y<n){
                    if(nums[x][y]==1){
                        nums[x][y]=-1;
                        if(x==0||x==m-1||y==0||y==n-1){
                            sign=true;
                        }
                        Q.push({x,y});
                    }
                }
            }
        }
    }
    res+=(sign==false);
}
int main(){
    int m,n;
    cin>>m>>n;
    vector<vector<int>>nums(m,vector<int>(n,0));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>nums[i][j];
        }
    }
    int res=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(nums[i][j]==1){
                bfs(i,j,nums,res);
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

#快手校招##快手##笔试题目#