快手笔试 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; }
这个题是树的一个变种,考察递归的理解和使用 。
主要是两个函数,一个是对树上的路径进行增加,一个是根据给定起点和终点求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; }