LeetCode 1311题解析：BFS实现好友视频推荐算法

1. 题目解析与需求拆解LeetCode 1311题获取你好友已观看的视频是一个典型的图论与数据结构结合的应用题。题目给定一个社交网络关系图friends数组、用户IDid、观看视频列表watchedVideos和层级数level要求返回指定用户在特定社交层级的好友观看的所有视频并按观看频率和字典序排序。1.1 核心数据结构分析题目涉及三个关键数据结构社交关系图用vectorvector 表示的无向图每个节点代表一个用户边代表好友关系视频观看记录vectorvector 结构每个用户对应一个字符串列表输出要求需要统计特定层级好友观看视频的频率并排序1.2 算法选择依据根据题目特性我们需要使用BFS遍历社交网络找出特定层级的所有好友用哈希表统计视频出现频率对统计结果进行多条件排序选择BFS而非DFS的原因是在社交网络这种图结构中BFS能更高效地按层级遍历节点正好匹配题目特定层级好友的需求。2. 解决方案设计与实现2.1 BFS层级遍历实现vectorstring watchedVideosByFriends(vectorvectorstring watchedVideos, vectorvectorint friends, int id, int level) { queueint q; vectorbool visited(friends.size(), false); q.push(id); visited[id] true; int currentLevel 0; while (!q.empty() currentLevel level) { int size q.size(); for (int i 0; i size; i) { int current q.front(); q.pop(); for (int friendId : friends[current]) { if (!visited[friendId]) { visited[friendId] true; q.push(friendId); } } } currentLevel; } // 后续处理... }关键点说明使用队列实现标准BFSvisited数组避免重复访问currentLevel变量精确控制遍历深度内层循环处理当前层级所有节点2.2 视频统计与排序unordered_mapstring, int videoCount; while (!q.empty()) { int current q.front(); q.pop(); for (string video : watchedVideos[current]) { videoCount[video]; } } vectorpairstring, int videos(videoCount.begin(), videoCount.end()); sort(videos.begin(), videos.end(), [](auto a, auto b) { return a.second b.second ? a.first b.first : a.second b.second; }); vectorstring result; for (auto p : videos) { result.push_back(p.first); } return result;排序逻辑解析使用unordered_map统计视频出现次数将map转为vector 便于排序自定义排序规则先按频率升序同频按字典序最终提取视频名称返回3. 复杂度分析与优化3.1 时间复杂度分解BFS部分O(VE)V为用户数E为好友关系数视频统计O(L×M)L为目标层级好友数M为平均每人观看视频数排序部分O(K log K)K为不同视频数量3.2 空间复杂度分析visited数组O(V)队列最坏O(V)哈希表O(K)排序临时数组O(K)3.3 实际优化技巧提前终止当currentLevel超过目标层级时可提前退出循环内存预分配result.reserve(videoCount.size())避免动态扩容移动语义使用emplace_back替代push_back减少字符串拷贝4. 常见问题与调试技巧4.1 典型错误案例案例1忽略无向图的处理// 错误写法没有标记起始节点为已访问 visited[id] true; // 必须放在q.push(id)之前 q.push(id);案例2层级控制错误// 错误写法错误的位置增加currentLevel while (!q.empty()) { int size q.size(); currentLevel; // 应该在内层循环结束后增加 for (int i 0; i size; i) { // ... } }4.2 调试检查清单边界检查id是否有效0 ≤ id friends.size()level是否为非负整数空输入处理图遍历验证确保所有边都被正确处理无向图要双向考虑检查visited数组的正确更新排序验证测试相同频率不同视频名的排序验证空视频列表的情况4.3 测试用例设计// 测试用例1基础功能验证 TEST_CASE(Basic functionality) { vectorvectorstring videos {{A,B}, {C}, {B,C}, {D}}; vectorvectorint friends {{1,2}, {0,3}, {0}, {1}}; auto res watchedVideosByFriends(videos, friends, 0, 1); REQUIRE(res vectorstring{B,C,A}); } // 测试用例2多层级验证 TEST_CASE(Multiple levels) { vectorvectorstring videos {{A}, {B}, {C}, {D}}; vectorvectorint friends {{1}, {0,2}, {1,3}, {2}}; auto res watchedVideosByFriends(videos, friends, 0, 2); REQUIRE(res vectorstring{C,D}); }5. 工程实践中的扩展思考5.1 实际应用场景这种算法模式可应用于社交网络的内容推荐系统病毒式营销的潜在受众分析网络安全中的信任度传播计算5.2 性能敏感场景优化当数据量极大时如千万级用户改用邻接表存储稀疏社交图使用并行BFS如使用MPI或CUDA对视频统计采用MapReduce模式5.3 C工程化实现建议使用const引用避免不必要的拷贝vectorstring watchedVideosByFriends(const vectorvectorstring watchedVideos, const vectorvectorint friends, int id, int level)添加noexcept修饰符当确定不会抛出异常时vectorstring watchedVideosByFriends(...) noexcept使用结构化绑定(C17)提升可读性for (auto [video, count] : videoCount) { // ... }在解决这类问题时最重要的是建立清晰的解题框架先明确数据结构和算法选择再处理边界条件和优化细节。实际编码时建议先用注释写出各步骤伪代码再逐步实现每个模块最后进行整体测试和优化。