核心代码编程-社交网络相同爱好好友查询-200分

题目描述在一个社交网络中用户之间通过关注关系形成有向图。每个用户有两个属性用户ID整数字符串兴趣标列表字符串数组现在需要实现一个函数查询在指定用户k跳内k度关系内其他用户的兴趣和给定用户兴趣相符的用户ID列表不含自己注意 兴趣相符是指两个用户的兴趣列表有交集。实现函数queryFriends(nodes, relations, myld, maxHop)输入参数1. nodes - 用户节点数据类型整数二维数组向量·每行表示一个用户包含[id兴趣1兴趣2,...]示例[0.music,reading表示用户0有2个兴趣music和reading·所有用户ID是0到n-1的连续整数对应的字符串2. relations - 关注关系类型整数二维数组向量每行表示一个关注关系关注者ID被关注者ID]示例[0,1表示用户0关注了用户13. myld - 起始用户ID示例04. maxHop - 最大跳数k示例 2返回值·内容所有满足条件的用户ID及共同的兴趣列表如[0, music, reading],[1, reading]]·格式1不同用户之间按以下规则排序按与起始用户的最短距离从小到大排序距离相同的用户按ID对应整数值进行从小到大排序格式2对于具体某用户与起始用户的共同兴趣列表按以下规则排序按照ascii码序从小到大排序·如果没有满足条件的用户返回空数组约束条件1用户数n:1≤n s 10^4可认为用户的id字符串对应整数范围符合该条件2关注关系数m:0≤ms2x10^4若关系任一端包含不存在的点应该自动忽略不影响原始查询诉求3最大跳数k: 1≤k≤100大于最大跳数按照上限100对待4. 每个用户最多10个兴趣标签可认为所有用户的兴趣个数符合该条件5给定查询条件中的起始用户ID一定存在示例1输入[[O, music,sports],[1, music, reading][2, music], [3play,music,sports]1,[[O,1], [1, 2], [2, 3], [0,3]],0,2输出[[1,music],[3,music,sports],[2,music]]说明从ID0出发兴趣相同(3跳内可以匹配到用户1、2、3同时用户1、3跳数少因此用户1、3在用户2之前。,又因为1相比于3整数序靠前因此用户1在用户3。用户3中匹配到了多项爱好根据字母序排列music在sports之前。示例2输入[[O, music], [1, music],[2, music], [3, music],[4, music]]1,[[0, 1], [1,2], [2, 3], [3, 4]],0,1输出[[1,music]]说明所有用户都满足兴趣条件但是跳数限制在1跳内因此仅用户1满足条件示例3输入[[0, music]],0,0,2输出[ ]说明不存在满足条件的结果返回空数组实现思路数据预处理解析用户节点数据构建用户ID到兴趣集合的映射。解析关注关系构建有向图的邻接表忽略无效节点。广度优先搜索(BFS)从起始用户myId开始计算在maxHop跳内所有可达用户的最短距离跳数。记录每个用户的距离并确保不超过最大跳数限制上限100。兴趣匹配对BFS得到的用户排除起始用户检查其兴趣与起始用户兴趣的交集。若有交集计算共同兴趣列表并按ASCII码序排序。结果排序与输出用户按最短距离升序排序距离相同则按ID整数值升序排序。输出格式为二维列表[[用户ID, 共同兴趣1, 共同兴趣2, ...], ...]。以下为各语言实现Pythonfrom collections import deque def queryFriends(nodes, relations, myId, maxHop): # 预处理用户兴趣 interests {} for node in nodes: user_id node[0] interests[user_id] set(node[1:]) # 构建有向图忽略无效关系 graph {} valid_users set(interests.keys()) for rel in relations: follower, followee rel if follower in valid_users and followee in valid_users: if follower not in graph: graph[follower] [] graph[follower].append(followee) # BFS计算最短距离 dist {} queue deque() dist[myId] 0 queue.append(myId) max_k min(maxHop, 100) # 跳数上限处理 while queue: current queue.popleft() current_dist dist[current] if current_dist max_k: continue if current in graph: for neighbor in graph[current]: if neighbor not in dist: dist[neighbor] current_dist 1 queue.append(neighbor) # 收集并过滤结果 result [] start_interests interests[myId] for user, d in dist.items(): if user myId: # 排除起始用户 continue common interests[user] start_interests if common: sorted_common sorted(common) # ASCII码序排序 result.append([user] sorted_common) # 用户排序先距离升序再ID整数值升序 result.sort(keylambda x: (dist[x[0]], int(x[0]))) return resultJavaimport java.util.*; public class Solution { public ListListString queryFriends(ListListString nodes, ListListString relations, String myId, int maxHop) { // 预处理用户兴趣 MapString, SetString interests new HashMap(); for (ListString node : nodes) { String userId node.get(0); SetString set new HashSet(node.subList(1, node.size())); interests.put(userId, set); } // 构建有向图忽略无效关系 MapString, ListString graph new HashMap(); SetString validUsers new HashSet(interests.keySet()); for (ListString rel : relations) { String follower rel.get(0); String followee rel.get(1); if (validUsers.contains(follower) validUsers.contains(followee)) { graph.computeIfAbsent(follower, k - new ArrayList()).add(followee); } } // BFS计算最短距离 MapString, Integer dist new HashMap(); QueueString queue new LinkedList(); dist.put(myId, 0); queue.offer(myId); int maxK Math.min(maxHop, 100); // 跳数上限处理 while (!queue.isEmpty()) { String current queue.poll(); int currentDist dist.get(current); if (currentDist maxK) continue; ListString neighbors graph.get(current); if (neighbors ! null) { for (String neighbor : neighbors) { if (!dist.containsKey(neighbor)) { dist.put(neighbor, currentDist 1); queue.offer(neighbor); } } } } // 收集并过滤结果 ListListString result new ArrayList(); SetString startInterests interests.get(myId); for (Map.EntryString, Integer entry : dist.entrySet()) { String user entry.getKey(); if (user.equals(myId)) continue; // 排除起始用户 SetString common new HashSet(interests.get(user)); common.retainAll(startInterests); if (!common.isEmpty()) { ListString sortedCommon new ArrayList(common); Collections.sort(sortedCommon); // ASCII码序排序 ListString item new ArrayList(); item.add(user); item.addAll(sortedCommon); result.add(item); } } // 用户排序先距离升序再ID整数值升序 result.sort((a, b) - { int distA dist.get(a.get(0)); int distB dist.get(b.get(0)); if (distA ! distB) return distA - distB; return Integer.parseInt(a.get(0)) - Integer.parseInt(b.get(0)); }); return result; } }JavaScriptfunction queryFriends(nodes, relations, myId, maxHop) { // 预处理用户兴趣 const interests new Map(); for (const node of nodes) { const userId node[0]; interests.set(userId, new Set(node.slice(1))); } // 构建有向图忽略无效关系 const graph new Map(); const validUsers new Set(interests.keys()); for (const rel of relations) { const [follower, followee] rel; if (validUsers.has(follower) validUsers.has(followee)) { if (!graph.has(follower)) { graph.set(follower, []); } graph.get(follower).push(followee); } } // BFS计算最短距离 const dist new Map(); const queue []; dist.set(myId, 0); queue.push(myId); const maxK Math.min(maxHop, 100); // 跳数上限处理 while (queue.length 0) { const current queue.shift(); const currentDist dist.get(current); if (currentDist maxK) continue; const neighbors graph.get(current); if (neighbors) { for (const neighbor of neighbors) { if (!dist.has(neighbor)) { dist.set(neighbor, currentDist 1); queue.push(neighbor); } } } } // 收集并过滤结果 const result []; const startInterests interests.get(myId); for (const [user, d] of dist) { if (user myId) continue; // 排除起始用户 const userInterests interests.get(user); const common [...userInterests].filter(x startInterests.has(x)); if (common.length 0) { common.sort(); // ASCII码序排序 result.push([user, ...common]); } } // 用户排序先距离升序再ID整数值升序 result.sort((a, b) { const distA dist.get(a[0]); const distB dist.get(b[0]); if (distA ! distB) return distA - distB; return parseInt(a[0]) - parseInt(b[0]); }); return result; }C#include vector #include string #include unordered_map #include unordered_set #include queue #include algorithm using namespace std; vectorvectorstring queryFriends(vectorvectorstring nodes, vectorvectorstring relations, string myId, int maxHop) { // 预处理用户兴趣 unordered_mapstring, unordered_setstring interests; for (auto node : nodes) { string userId node[0]; interests[userId] unordered_setstring(node.begin() 1, node.end()); } // 构建有向图忽略无效关系 unordered_mapstring, vectorstring graph; unordered_setstring validUsers; for (auto kv : interests) validUsers.insert(kv.first); for (auto rel : relations) { string follower rel[0], followee rel[1]; if (validUsers.find(follower) ! validUsers.end() validUsers.find(followee) ! validUsers.end()) { graph[follower].push_back(followee); } } // BFS计算最短距离 unordered_mapstring, int dist; queuestring q; dist[myId] 0; q.push(myId); int maxK min(maxHop, 100); // 跳数上限处理 while (!q.empty()) { string current q.front(); q.pop(); int currentDist dist[current]; if (currentDist maxK) continue; auto neighbors graph.find(current); if (neighbors ! graph.end()) { for (string neighbor : neighbors-second) { if (dist.find(neighbor) dist.end()) { dist[neighbor] currentDist 1; q.push(neighbor); } } } } // 收集并过滤结果 vectorvectorstring result; auto startInterests interests[myId]; for (auto kv : dist) { string user kv.first; if (user myId) continue; // 排除起始用户 auto userInterests interests[user]; vectorstring common; for (auto interest : userInterests) { if (startInterests.find(interest) ! startInterests.end()) { common.push_back(interest); } } if (!common.empty()) { sort(common.begin(), common.end()); // ASCII码序排序 vectorstring item {user}; item.insert(item.end(), common.begin(), common.end()); result.push_back(item); } } // 用户排序先距离升序再ID整数值升序 sort(result.begin(), result.end(), [](vectorstring a, vectorstring b) { int distA dist[a[0]], distB dist[b[0]]; if (distA ! distB) return distA distB; return stoi(a[0]) stoi(b[0]); }); return result; }Gopackage main import ( sort ) func queryFriends(nodes [][]string, relations [][]string, myId string, maxHop int) [][]string { // 预处理用户兴趣 interests : make(map[string]map[string]bool) for _, node : range nodes { userId : node[0] interests[userId] make(map[string]bool) for _, interest : range node[1:] { interests[userId][interest] true } } // 构建有向图忽略无效关系 graph : make(map[string][]string) validUsers : make(map[string]bool) for user : range interests { validUsers[user] true } for _, rel : range relations { follower, followee : rel[0], rel[1] if validUsers[follower] validUsers[followee] { graph[follower] append(graph[follower], followee) } } // BFS计算最短距离 dist : make(map[string]int) queue : []string{myId} dist[myId] 0 maxK : maxHop if maxK 100 { maxK 100 } for len(queue) 0 { current : queue[0] queue queue[1:] currentDist : dist[current] if currentDist maxK { continue } for _, neighbor : range graph[current] { if _, exists : dist[neighbor]; !exists { dist[neighbor] currentDist 1 queue append(queue, neighbor) } } } // 收集并过滤结果 result : [][]string{} startInterests : interests[myId] for user, d : range dist { if user myId { // 排除起始用户 continue } common : []string{} for interest : range interests[user] { if startInterests[interest] { common append(common, interest) } } if len(common) 0 { sort.Strings(common) // ASCII码序排序 item : append([]string{user}, common...) result append(result, item) } } // 用户排序先距离升序再ID整数值升序 sort.Slice(result, func(i, j int) bool { distI : dist[result[i][0]] distJ : dist[result[j][0]] if distI ! distJ { return distI distJ } return toInt(result[i][0]) toInt(result[j][0]) }) return result } func toInt(s string) int { res : 0 for _, c : range s { res res*10 int(c-0) } return res }C#include stdio.h #include stdlib.h #include string.h #define MAX_USERS 10000 #define MAX_INTERESTS 10 typedef struct { char** items; int size; } StringList; typedef struct { StringList* data; int size; } ResultList; int compareStrings(const void* a, const void* b) { return strcmp(*(const char**)a, *(const char**)b); } int toInt(const char* s) { int res 0; while (*s) { res res * 10 (*s - 0); s; } return res; } ResultList queryFriends(char*** nodes, int nodesSize, int* nodesColSize, char*** relations, int relationsSize, char* myId, int maxHop) { // 预处理用户兴趣 char*** interests (char***)malloc(MAX_USERS * sizeof(char**)); int* interestCount (int*)calloc(MAX_USERS, sizeof(int)); for (int i 0; i nodesSize; i) { int userId atoi(nodes[i][0]); interestCount[userId] nodesColSize[i] - 1; interests[userId] (char**)malloc(interestCount[userId] * sizeof(char*)); for (int j 0; j interestCount[userId]; j) { interests[userId][j] nodes[i][j1]; } } // 构建有向图忽略无效关系 int** graph (int**)malloc(MAX_USERS * sizeof(int*)); int* graphSize (int*)calloc(MAX_USERS, sizeof(int)); int* validUsers (int*)calloc(MAX_USERS, sizeof(int)); for (int i 0; i nodesSize; i) { int userId atoi(nodes[i][0]); validUsers[userId] 1; } for (int i 0; i relationsSize; i) { int follower atoi(relations[i][0]); int followee atoi(relations[i][1]); if (validUsers[follower] validUsers[followee]) { graph[follower] (int*)realloc(graph[follower], (graphSize[follower] 1) * sizeof(int)); graph[follower][graphSize[follower]] followee; } } // BFS计算最短距离 int* dist (int*)malloc(MAX_USERS * sizeof(int)); for (int i 0; i MAX_USERS; i) dist[i] -1; int* queue (int*)malloc(MAX_USERS * sizeof(int)); int front 0, rear 0; int startId atoi(myId); dist[startId] 0; queue[rear] startId; int maxK maxHop 100 ? 100 : maxHop; while (front rear) { int current queue[front]; int currentDist dist[current]; if (currentDist maxK) continue; for (int i 0; i graphSize[current]; i) { int neighbor graph[current][i]; if (dist[neighbor] -1) { dist[neighbor] currentDist 1; queue[rear] neighbor; } } } // 收集并过滤结果 ResultList result; result.size 0; result.data (StringList*)malloc(MAX_USERS * sizeof(StringList)); for (int i 0; i MAX_USERS; i) { if (dist[i] -1 || i startId) continue; // 排除起始用户 StringList common; common.size 0; common.items (char**)malloc(MAX_INTERESTS * sizeof(char*)); for (int j 0; j interestCount[i]; j) { for (int k 0; k interestCount[startId]; k) { if (strcmp(interests[i][j], interests[startId][k]) 0) { common.items[common.size] interests[i][j]; break; } } } if (common.size 0) { qsort(common.items, common.size, sizeof(char*), compareStrings); // ASCII码序排序 result.data[result.size].size common.size 1; result.data[result.size].items (char**)malloc((common.size 1) * sizeof(char*)); char userIdStr[10]; sprintf(userIdStr, %d, i); result.data[result.size].items[0] strdup(userIdStr); for (int j 0; j common.size; j) { result.data[result.size].items[j1] strdup(common.items[j]); } result.size; } free(common.items); } // 用户排序先距离升序再ID整数值升序 for (int i 0; i result.size; i) { for (int j i 1; j result.size; j) { int idI toInt(result.data[i].items[0]); int idJ toInt(result.data[j].items[0]); int distI dist[idI], distJ dist[idJ]; if (distI ! distJ) { if (distI distJ) { StringList temp result.data[i]; result.data[i] result.data[j]; result.data[j] temp; } } else if (idI idJ) { StringList temp result.data[i]; result.data[i] result.data[j]; result.data[j] temp; } } } // 清理临时内存 for (int i 0; i MAX_USERS; i) { if (interests[i]) free(interests[i]); if (graph[i]) free(graph[i]); } free(interests); free(graph); free(graphSize); free(validUsers); free(dist); free(queue); return result; }