4月26日快手工程C笔试题解
第一题大概意思是每个域名下面有一定的路径,如果两个域名下的请求路径完全相同,那么就把两个域名视为相同的,最后输出有多少组相同的就可以。
既然是集合第一时间想到的是STL的set,STL里面set已经重载了小于号,可以很轻易的判断是否相等。
把每个请求分成地址和路径,然后把路径存到地址对应的集合里面,为了比较方便,把路径做了哈希。
既然是集合第一时间想到的是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; }
第四题参考LeetCode 1254(https://leetcode-cn.com/problems/number-of-closed-islands/)
#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; }