华为OD机试 新系统 C++实现【社交网络相同爱好好友查询】

社交网络相同爱好好友查询华为OD新系统机试真题 华为OD新系统上机考试真题 5月13号 200分题型本题更多语言题解可点击查看:华为OD机试新系统真题 - 社交网络相同爱好好友查询(C/C/Py/Java/Js/Go)题解题目内容在一个社交网络中用户之间通过关注关系形成有向图。每个用户有两个属性用户I D IDID整数字符串兴趣标签列表字符串数组现在需要实现一个函数查询在指定用户k kk跳内k kk度关系内其他用户的兴趣和给定用户兴趣相符的用户I D IDID列表不含自己。注意兴趣相符是指两个用户的兴趣列表有交集。实现函数q u e r y F r i e n d s ( n o d e s , r e l a t i o n s , m y I d , m a x H o p ) queryFriends(nodes, relations, myId, maxHop)queryFriends(nodes,relations,myId,maxHop)输入参数n o d e s nodesnodes- 用户节点数据类型整数二维数组/向量每行表示一个用户包含[i d idid, 兴趣1 11, 兴趣2 22, …]示例[“0 00”, “m u s i c musicmusic”, “r e a d i n g readingreading”] 表示用户0 00有2 22个兴趣m u s i c musicmusic和r e a d i n g readingreading所有用户I D IDID是0 00到n − 1 n-1n−1的连续整数对应的字符串r e l a t i o n s relationsrelations- 关注关系类型整数二维数组/向量每行表示一个关注关系[关注者I D IDID, 被关注者I D IDID]示例[“0 00”, “1 11”] 表示用户0 00关注了用户1 11m y I d myIdmyId- 起始用户I D IDID示例“0 00”m a x H o p maxHopmaxHop- 最大跳数k kk示例2 22返回值内容所有满足条件的用户I D IDID及共同的兴趣列表如[[“0 00”, “m u s i c musicmusic”, “r e a d i n g readingreading”],[“1 11”, “r e a d i n g readingreading”]]格式1 11不同用户之间按以下规则排序按与起始用户的最短距离从小到大排序距离相同的用户按ID对应整数值进行从小到大排序格式2 22对于具体某用户与起始用户的共同兴趣列表按以下规则排序 按照a s c i i asciiascii码序从小到大排序如果没有满足条件的用户返回空数组约束条件用户数n : 1 ≤ n ≤ 10 4 n: 1 ≤ n ≤ 10^4n:1≤n≤104可认为用户的i d idid字符串对应整数范围符合该条件关注关系数m : 0 ≤ m ≤ 2 × 10 4 m: 0 ≤ m ≤ 2×10^4m:0≤m≤2×104若关系任一端包含不存在的点应该自动忽略不影响原始查询诉求最大跳数k : 1 ≤ k ≤ 100 k: 1 ≤ k ≤ 100k:1≤k≤100大于最大跳数按照上限100 100100对待每个用户最多10 1010个兴趣标签可认为所有用户的兴趣个数符合该条件给定查询条件中的起始用户I D IDID一定存在样例1输入0,music,sports 1,music,reading 2,music 3,play,music,sports 0,1 1,2 2,3 0,3 0 2输出1,music 3,music,sports 2,music说明从I D IDID“0 00” 出发兴趣相同2 22跳内可以匹配到用户1 11、“2 22”、“3 33”同时用户1 11、“3 33跳数少因此用户1 11”、“3 33在用户2 22之前。又因为1 11相比于3 33整数序靠前因此用户1 11在用户3 33”。用户3 33中匹配到了多项爱好根据字母序排列m u s i c musicmusic在s p o r t s sportssports之前。样例2输入0,music 1,music 2,music 3music 4,music 0,1 1,2 2,3 3,4 0 1输出1,music说明所有用户都满足兴趣条件但是跳数限制在1 11跳内因此仅用户1 11满足条件样例3输入0,music 0 2输出说明不存在满足条件的结果无输出题解思路BFS先提取出每个用户的兴趣爱好根据id进行保存将用户作为节点关注关系看作有向边。根据输入关注关系创建对应邻接表。指定k跳级就是用户之间的距离用户之间的距离可以使用最短路算法或者BFS算法实现下面代码利用BFS计算其它用户与指定用户的距离。使用dist数组存储其它用户与指定用户距离。具体逻辑为初始将myId加入队列中,更新dist[myId] 0每次从队列中取出队首元素current更新相邻节点的距离,对应节点node处理如下如果dist[node] ! -1说明之前已访问不做处理dist[node] 1的情况更新对应距离为dist[node] dist[current] 1,如果dist[node] maxHop不加入队列(本题距离大于maxHop可认为不可达)。否则加入队列中。重复执行2的逻辑直到队列为空。利用dist找到可达用户并且提取出拥有公共爱好的用户加入结果数组中。共同爱好需要进行排序按照题目要求利用dist进行自定义按与起始用户的最短距离从小到大排序 距离相同的用户按ID对应整数值进行从小到大排序规则排序。c#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includemap #includequeue using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vectorstring split(const string str, const string delimiter) { vectorstring result; size_t start 0; size_t end str.find(delimiter); while (end ! string::npos) { result.push_back(str.substr(start, end - start)); start end delimiter.length(); end str.find(delimiter, start); } // 添加最后一个部分 result.push_back(str.substr(start)); return result; } vectorstring findSameLike(vectorstring a, vectorstring b) { if (a.empty() || b.empty()) { return {}; } vectorstring res; for (int i 0; i a.size(); i) { string item a[i]; for (int j 0; j b.size(); j) { if (b[j] item) { res.push_back(item); } } } return res; } vectorvectorstring queryFriends(vectorvectorstring nodes, vectorvectorstring relations, string myId, int maxHop) { int n nodes.size(); // 限制不超过100 maxHop min(maxHop, 100); vectorvectorint graph(n); // 根据关注关系建表 for (auto relation : relations) { int u stoi(relation[0]); int v stoi(relation[1]); // 存在不存在的点 if (u 0 || v 0 || u n - 1 || v n - 1) { continue; } graph[u].push_back(v); } // 映射每个用户的爱好 vectorvectorstring like(n); for (auto node : nodes) { string id node[0]; int idValue stoi(id); for (int j 1; j node.size(); j) { like[idValue].push_back(node[j]); } } // 处于指定用户跳数 vectorint dist(n, -1); int myIdValue stoi(myId); //指定用户不存在爱好情况肯定没有结果 if (like[myIdValue].empty()) { return {}; } // 使用BFS求跳数 queueint q; q.push(myIdValue); dist[myIdValue] 0; while (!q.empty()) { int current q.front(); q.pop(); for (auto v : graph[current]) { if (dist[v] ! -1) { continue; } dist[v] dist[current] 1; if (dist[v] maxHop) { q.push(v); } } } vectorvectorstring res; // 找出具备相同爱好并且在指定跳内的结果 for (int i 0; i n; i) { if (dist[i] -1) { continue; } if (i myIdValue) { continue; } vectorstring sameLike findSameLike(like[i], like[myIdValue]); if (sameLike.empty()) { continue; } // 将爱好升序 sort(sameLike.begin(), sameLike.end()); vectorstring item; item.push_back(to_string(i)); for (string s : sameLike) { item.push_back(s); } res.push_back(item); } // 自定义进行排序 sort(res.begin(), res.end(), [](vectorstringa , vectorstring b) { int id1 stoi(a[0]); int id2 stoi(b[0]); if (dist[id1] dist[id2]) { return id1 id2; } return dist[id1] dist[id2]; }); return res; } int main() { string input1,input2,myId,maxHopStr; getline(cin, input1); getline(cin, input2); getline(cin, myId); getline(cin, maxHopStr); vectorvectorstring nodes; vectorstring tmp; if (!input1.empty()) { tmp split(input1, ); for (int i 0; i tmp.size(); i) { nodes.push_back(split(tmp[i], ,)); } } vectorvectorstring relations; if (!input2.empty()) { tmp split(input2, ); for (int i 0; i tmp.size(); i) { relations.push_back(split(tmp[i], ,)); } } vectorvectorstring res queryFriends(nodes, relations, myId, stoi(maxHopStr)); // 输出结果 for (int i 0; i res.size(); i) { vectorstring current res[i]; for (int j 0; j current.size(); j) { if (j ! 0) { cout ,; } cout current[j]; } cout endl; } }JAVAimportjava.util.*;publicclassMain{publicstaticListListStringqueryFriends(ListListStringnodes,ListListStringrelations,StringmyId,intmaxHop){intnnodes.size();// 限制不超过100maxHopMath.min(maxHop,100);// 根据关注关系建表ListListIntegergraphnewArrayList();for(inti0;in;i)graph.add(newArrayList());for(ListStringr:relations){intuInteger.parseInt(r.get(0));intvInteger.parseInt(r.get(1));// 存在不存在的点if(u0||un||v0||vn)continue;graph.get(u).add(v);}// 映射每个用户的爱好ListListStringlikenewArrayList();for(inti0;in;i)like.add(newArrayList());for(ListStringnode:nodes){intidInteger.parseInt(node.get(0));for(inti1;inode.size();i){like.get(id).add(node.get(i));}}// 处于指定用户跳数int[]distnewint[n];Arrays.fill(dist,-1);intmyIdValueInteger.parseInt(myId);// 指定用户不存在爱好情况肯定没有结果if(like.get(myIdValue).isEmpty()){returnnewArrayList();}// 使用BFS求跳数QueueIntegerqnewLinkedList();q.offer(myIdValue);dist[myIdValue]0;while(!q.isEmpty()){intcurq.poll();for(intv:graph.get(cur)){if(dist[v]!-1)continue;dist[v]dist[cur]1;if(dist[v]maxHop){q.offer(v);}}}ListListStringresnewArrayList();// 找出具备相同爱好并且在指定跳内的结果for(inti0;in;i){if(dist[i]-1)continue;if(imyIdValue)continue;ListStringsameLikenewArrayList();for(Stringa:like.get(i)){for(Stringb:like.get(myIdValue)){if(a.equals(b))sameLike.add(a);}}if(sameLike.isEmpty())continue;// 将爱好升序Collections.sort(sameLike);ListStringitemnewArrayList();item.add(String.valueOf(i));item.addAll(sameLike);res.add(item);}// 自定义进行排序res.sort((a,b)-{intid1Integer.parseInt(a.get(0));intid2Integer.parseInt(b.get(0));if(dist[id1]dist[id2])returnid1-id2;returndist[id1]-dist[id2];});returnres;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringinput1sc.nextLine();Stringinput2sc.nextLine();StringmyIdsc.nextLine();intmaxHopInteger.parseInt(sc.nextLine());ListListStringnodesnewArrayList();ListListStringrelationsnewArrayList();if(!input1.isEmpty()){for(Strings:input1.split( )){nodes.add(Arrays.asList(s.split(,)));}}if(!input2.isEmpty()){for(Strings:input2.split( )){relations.add(Arrays.asList(s.split(,)));}}ListListStringresqueryFriends(nodes,relations,myId,maxHop);for(ListStringr:res){System.out.println(String.join(,,r));}}}