1. 题目解析与需求拆解LeetCode 1311这道题描述了一个社交网络中的视频观看记录查询场景给定一个用户的朋友关系网络和朋友观看的视频列表要求找出指定层级好友观看的所有视频并按观看频率和字母顺序排序输出。这个题目本质上考察的是图遍历和数据处理能力。我们需要从起始用户出发找到所有k层深度的好友即广度优先搜索BFS的经典应用场景然后统计这些好友观看的视频频次最后按照题目要求的规则排序输出。关键点提示题目中的k层好友指的是最短距离为k的朋友不是累计距离不超过k的所有朋友。这一点在BFS实现时需要特别注意。2. 算法设计与实现思路2.1 数据结构选择首先我们需要选择合适的数据结构来表示题目中的各个元素朋友关系图使用邻接表表示最为合适可以用vectorvectorint或者unordered_mapint, vectorint来存储视频记录每个用户对应一个视频列表可以用vectorvectorstring存储结果统计需要统计视频出现次数和排序unordered_mapstring, int适合做频次统计// 典型的数据结构定义示例 vectorvectorint friends; // 朋友关系图 vectorvectorstring watchedVideos; // 每个用户观看的视频 unordered_mapstring, int videoCount; // 视频频次统计2.2 核心算法流程完整的算法流程可以分为三个主要步骤BFS遍历找到k层好友使用队列实现标准BFS记录每个节点的访问层级当遇到层级等于k时收集用户ID统计视频观看频次遍历所有k层好友对每个好友观看的视频进行计数使用哈希表记录每个视频的出现次数排序输出结果首先按观看次数升序排序次数相同的按字母顺序排序可以使用自定义排序函数实现2.3 边界条件处理在实际编码中需要考虑以下边界情况起始用户ID无效的情况k0时应该返回用户自己观看的视频某些用户没有观看任何视频朋友关系图为空的情况3. 详细代码实现与解析3.1 BFS实现查找k层好友vectorint getKLevelFriends(int n, vectorvectorint friends, int id, int k) { vectorbool visited(n, false); queuepairint, int q; // {user, level} vectorint result; q.push({id, 0}); visited[id] true; while (!q.empty()) { auto [user, level] q.front(); q.pop(); if (level k) { result.push_back(user); continue; // 不需要再处理更深层的朋友 } for (int friendId : friends[user]) { if (!visited[friendId]) { visited[friendId] true; q.push({friendId, level 1}); } } } return result; }这段代码实现了标准的BFS遍历特别注意使用pair同时记录用户ID和当前层级当层级等于k时收集结果并跳过进一步处理使用visited数组避免重复访问3.2 视频频次统计与排序vectorstring getWatchedVideos(vectorint users, vectorvectorstring watchedVideos) { unordered_mapstring, int count; // 统计视频出现次数 for (int user : users) { for (string video : watchedVideos[user]) { count[video]; } } // 转换为vector便于排序 vectorpairstring, int videos(count.begin(), count.end()); // 自定义排序 auto cmp [](const pairstring, int a, const pairstring, int b) { return a.second b.second ? a.first b.first : a.second b.second; }; sort(videos.begin(), videos.end(), cmp); // 提取结果 vectorstring result; for (auto [video, cnt] : videos) { result.push_back(video); } return result; }这段代码的关键点使用哈希表高效统计频次自定义排序函数实现题目要求的排序规则使用C17的结构化绑定简化代码3.3 完整解决方案将上述两部分组合起来得到完整解法class Solution { public: vectorstring watchedVideosByFriends(vectorvectorstring watchedVideos, vectorvectorint friends, int id, int k) { int n friends.size(); vectorbool visited(n, false); queuepairint, int q; vectorint kLevelFriends; // BFS找k层好友 q.push({id, 0}); visited[id] true; while (!q.empty()) { auto [user, level] q.front(); q.pop(); if (level k) { kLevelFriends.push_back(user); continue; } for (int friendId : friends[user]) { if (!visited[friendId]) { visited[friendId] true; q.push({friendId, level 1}); } } } // 统计视频频次 unordered_mapstring, int count; for (int user : kLevelFriends) { for (string video : watchedVideos[user]) { count[video]; } } // 排序 vectorpairstring, int videos(count.begin(), count.end()); auto cmp [](const pairstring, int a, const pairstring, int b) { return a.second b.second ? a.first b.first : a.second b.second; }; sort(videos.begin(), videos.end(), cmp); // 构造结果 vectorstring result; for (auto [video, cnt] : videos) { result.push_back(video); } return result; } };4. 复杂度分析与优化思路4.1 时间复杂度分析BFS部分O(V E)其中V是用户数量E是朋友关系数量视频统计部分O(M)M是所有k层好友观看的视频总数排序部分O(N log N)N是不同视频的数量总体时间复杂度为O(V E M N log N)在LeetCode的约束条件下是完全可行的。4.2 空间复杂度分析访问标记数组O(V)队列最坏情况O(V)哈希表O(N)排序辅助数组O(N)总体空间复杂度为O(V N)。4.3 可能的优化方向双向BFS当k值较大时可以考虑从两端同时搜索预处理如果需要多次查询可以预处理所有用户之间的最短距离并行统计对于大规模数据可以并行统计不同好友的视频观看情况5. 常见错误与调试技巧5.1 常见错误类型层级计算错误错误地将累计距离不超过k的朋友都包含进来解决方法在BFS中严格判断level k时才收集结果排序规则错误只按频次或只按字母排序解决方法自定义排序函数必须同时考虑两个条件重复计数同一个用户被多次统计解决方法确保BFS中使用visited数组5.2 调试技巧打印中间结果// 在BFS后打印找到的好友 cout K-level friends: ; for (int user : kLevelFriends) cout user ; cout endl;检查边界条件特别测试k0和k1的情况测试起始用户没有朋友的情况小规模测试用例/* 测试用例 用户0的朋友[1,2] 用户1的朋友[0,3] 用户2的朋友[0] 用户3的朋友[1] 观看视频[[A,B], [C], [B,C], [A]] id0, k1 应该返回 [A,B,C] */6. 相似题目与扩展思考6.1 LeetCode相似题目推荐127. Word Ladder同样使用BFS的最短路径问题133. Clone Graph图的遍历与复制347. Top K Frequent Elements频次统计与排序692. Top K Frequent Words更接近本题的字符串频次排序6.2 实际应用扩展这个问题可以扩展到很多实际场景社交网络推荐系统基于好友关系推荐内容病毒传播分析模拟信息在社交网络中的传播网络安全分析识别特定距离内的关联节点6.3 算法选择思考为什么本题使用BFS而不是DFSBFS天然适合查找最短路径/最小距离DFS可能会先深入某些路径导致层级判断复杂BFS的队列结构便于按层级处理节点7. 不同语言实现对比7.1 Python实现特点def watchedVideosByFriends(self, watchedVideos, friends, id, k): from collections import deque, defaultdict # BFS找k层好友 queue deque([(id, 0)]) visited {id} k_friends [] while queue: user, level queue.popleft() if level k: k_friends.append(user) continue for friend in friends[user]: if friend not in visited: visited.add(friend) queue.append((friend, level 1)) # 统计视频频次 count defaultdict(int) for user in k_friends: for video in watchedVideos[user]: count[video] 1 # 排序并返回 return [video for video, _ in sorted(count.items(), keylambda x: (x[1], x[0]))]Python实现注意点使用collections.deque实现高效队列defaultdict简化频次统计排序使用元组比较实现多条件排序7.2 Java实现特点public ListString watchedVideosByFriends(ListListString watchedVideos, ListListInteger friends, int id, int k) { // BFS找k层好友 Queueint[] queue new LinkedList(); boolean[] visited new boolean[friends.size()]; queue.offer(new int[]{id, 0}); visited[id] true; ListInteger kFriends new ArrayList(); while (!queue.isEmpty()) { int[] curr queue.poll(); if (curr[1] k) { kFriends.add(curr[0]); continue; } for (int friend : friends.get(curr[0])) { if (!visited[friend]) { visited[friend] true; queue.offer(new int[]{friend, curr[1] 1}); } } } // 统计视频频次 MapString, Integer count new HashMap(); for (int user : kFriends) { for (String video : watchedVideos.get(user)) { count.put(video, count.getOrDefault(video, 0) 1); } } // 排序 ListMap.EntryString, Integer list new ArrayList(count.entrySet()); list.sort((a, b) - { if (a.getValue().equals(b.getValue())) { return a.getKey().compareTo(b.getKey()); } return a.getValue() - b.getValue(); }); // 构造结果 ListString result new ArrayList(); for (Map.EntryString, Integer entry : list) { result.add(entry.getKey()); } return result; }Java实现注意点使用Queue接口和LinkedList实现队列Map和getOrDefault简化频次统计自定义Comparator实现多条件排序8. 实际工程中的考虑在实际工程项目中处理类似问题时还需要考虑数据规模当用户量很大时需要考虑分布式处理实时性要求是否需要实时计算还是可以预处理数据更新频率朋友关系和观看视频的更新频率如何内存限制对于特别大的图需要考虑内存友好的表示方法一个可能的优化是使用邻接表压缩存储朋友关系或者使用数据库存储朋友关系通过SQL查询特定距离的好友。对于视频频次统计可以考虑使用概率数据结构如Count-Min Sketch来节省内存特别是当视频种类非常多时。
技术解析与应用)
)
)
