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;
}
