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

1. 题目解析与需求拆解

LeetCode 1311题"获取你好友已观看的视频"是一个典型的图论与数据结构结合的应用题。题目给定一个社交网络关系图（friends数组）、用户ID（id）、观看视频列表（watchedVideos）和层级数（level），要求返回指定用户在特定社交层级的好友观看的所有视频，并按观看频率和字典序排序。

1.1 核心数据结构分析

题目涉及三个关键数据结构：

1. 社交关系图：用vector<vector >表示的无向图，每个节点代表一个用户，边代表好友关系
2. 视频观看记录：vector<vector >结构，每个用户对应一个字符串列表
3. 输出要求：需要统计特定层级好友观看视频的频率并排序

1.2 算法选择依据

根据题目特性，我们需要：

1. 使用BFS遍历社交网络，找出特定层级的所有好友
2. 用哈希表统计视频出现频率
3. 对统计结果进行多条件排序

选择BFS而非DFS的原因是：在社交网络这种图结构中，BFS能更高效地按层级遍历节点，正好匹配题目"特定层级好友"的需求。

2. 解决方案设计与实现

2.1 BFS层级遍历实现

vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) { queue<int> q; vector<bool> 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++; } // 后续处理... }

关键点说明：

1. 使用队列实现标准BFS
2. visited数组避免重复访问
3. currentLevel变量精确控制遍历深度
4. 内层循环处理当前层级所有节点

2.2 视频统计与排序

unordered_map<string, int> videoCount; while (!q.empty()) { int current = q.front(); q.pop(); for (string& video : watchedVideos[current]) { videoCount[video]++; } } vector<pair<string, 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; }); vector<string> result; for (auto& p : videos) { result.push_back(p.first); } return result;

排序逻辑解析：

1. 使用unordered_map统计视频出现次数
2. 将map转为vector 便于排序
3. 自定义排序规则：先按频率升序，同频按字典序
4. 最终提取视频名称返回

3. 复杂度分析与优化

3.1 时间复杂度分解

1. BFS部分：O(V+E)，V为用户数，E为好友关系数
2. 视频统计：O(L×M)，L为目标层级好友数，M为平均每人观看视频数
3. 排序部分：O(K log K)，K为不同视频数量

3.2 空间复杂度分析

1. visited数组：O(V)
2. 队列：最坏O(V)
3. 哈希表：O(K)
4. 排序临时数组：O(K)

3.3 实际优化技巧

1. 提前终止：当currentLevel超过目标层级时可提前退出循环
2. 内存预分配：result.reserve(videoCount.size())避免动态扩容
3. 移动语义：使用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 调试检查清单

1. 边界检查：

   • id是否有效（0 ≤ id < friends.size()）
   • level是否为非负整数
   • 空输入处理

2. 图遍历验证：

   • 确保所有边都被正确处理（无向图要双向考虑）
   • 检查visited数组的正确更新

3. 排序验证：

   • 测试相同频率不同视频名的排序
   • 验证空视频列表的情况

4.3 测试用例设计

// 测试用例1：基础功能验证 TEST_CASE("Basic functionality") { vector<vector<string>> videos = {{"A","B"}, {"C"}, {"B","C"}, {"D"}}; vector<vector<int>> friends = {{1,2}, {0,3}, {0}, {1}}; auto res = watchedVideosByFriends(videos, friends, 0, 1); REQUIRE(res == vector<string>{"B","C","A"}); } // 测试用例2：多层级验证 TEST_CASE("Multiple levels") { vector<vector<string>> videos = {{"A"}, {"B"}, {"C"}, {"D"}}; vector<vector<int>> friends = {{1}, {0,2}, {1,3}, {2}}; auto res = watchedVideosByFriends(videos, friends, 0, 2); REQUIRE(res == vector<string>{"C","D"}); }

5. 工程实践中的扩展思考

5.1 实际应用场景

这种算法模式可应用于：

1. 社交网络的内容推荐系统
2. 病毒式营销的潜在受众分析
3. 网络安全中的信任度传播计算

5.2 性能敏感场景优化

当数据量极大时（如千万级用户）：

1. 改用邻接表存储稀疏社交图
2. 使用并行BFS（如使用MPI或CUDA）
3. 对视频统计采用MapReduce模式

5.3 C++工程化实现建议

1. 使用const引用避免不必要的拷贝：

vector<string> watchedVideosByFriends(const vector<vector<string>>& watchedVideos, const vector<vector<int>>& friends, int id, int level)

2. 添加noexcept修饰符（当确定不会抛出异常时）：

vector<string> watchedVideosByFriends(...) noexcept

3. 使用结构化绑定(C++17)提升可读性：

for (auto& [video, count] : videoCount) { // ... }

在解决这类问题时，最重要的是建立清晰的解题框架：先明确数据结构和算法选择，再处理边界条件和优化细节。实际编码时建议先用注释写出各步骤伪代码，再逐步实现每个模块，最后进行整体测试和优化。