【C++BFS】1311. 获取你好友已观看的视频

本文涉及知识点

C++BFS算法

LeetCode1311. 获取你好友已观看的视频

有 n 个人，每个人都有一个 0 到 n-1 的唯一 id 。
给你数组 watchedVideos 和 friends ，其中 watchedVideos[i] 和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。
Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看过的视频，以此类推。一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好友观看过的视频。
给定你的 id 和一个 level 值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按字母顺序从小到大排列。
示例 1：

输入：watchedVideos = [[“A”,“B”],[“C”],[“B”,“C”],[“D”]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1
输出：[“B”,“C”]
解释：
你的 id 为 0（绿色），你的朋友包括（黄色）：
id 为 1 -> watchedVideos = [“C”]
id 为 2 -> watchedVideos = [“B”,“C”]
你朋友观看过视频的频率为：
B -> 1
C -> 2
示例 2：

输入：watchedVideos = [[“A”,“B”],[“C”],[“B”,“C”],[“D”]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2
输出：[“D”]
解释：
你的 id 为 0（绿色），你朋友的朋友只有一个人，他的 id 为 3（黄色）。

提示：

n == watchedVideos.length == friends.length
2 <= n <= 100
1 <= watchedVideos[i].length <= 100
1 <= watchedVideos[i][j].length <= 8
0 <= friends[i].length < n
0 <= friends[i][j] < n
0 <= id < n
1 <= level < n
如果 friends[i] 包含 j ，那么 friends[j] 包含 i

题解

一，通过BFS求出第leve 层朋友。
二，利用哈希映射mVideoCnt记录leve层朋友看的视频及次数。
三，有序映射sCntVideo记录：观看次数、视频名称。
四，按sCntVideo顺序返回视频名称。
BFS的状态表示：leves[0] = {id}，leves[i]记录leves[i-1]的直接朋友。
BFS的状态表示：通过next枚举cur的直接朋友。
BFS的初始状态：leves[0] = {id}
BFS的返回值：leves[leve]
BFS的出重处理：数组vis出重。

代码

核心代码

class Solution {public:vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {const int N = watchedVideos.size();vector<vector<int>> leves = { {id} };vector<bool> vis(N);vis[id] = true;for (int i = 0; i < leves.size(); i++) {vector<int> nexts;for (const auto& cur : leves[i]) {for (const auto& next : friends[cur]) {if (vis[next]) { continue; }vis[next] = true;nexts.emplace_back(next);}}if (nexts.empty()) { break; }leves.emplace_back(nexts);}if (level >= leves.size()) { return {}; };unordered_map<string, int> mVideoCnt;for (const auto& i : leves[level]) {for (const auto& s : watchedVideos[i]) {mVideoCnt[s]++;}}set<pair<int, string>> sCntVideo;for (const auto& [s, cnt] : mVideoCnt) {sCntVideo.emplace(cnt, s);}vector<string> ret;for (const auto& [tmp, s] : sCntVideo) {ret.emplace_back(s);}return ret;}};

单元测试

vector<vector<string>> watchedVideos;vector<vector<int>> friends;int id, level;TEST_METHOD(TestMethod1){watchedVideos = { {"A","B"},{"C"},{"B","C"},{"D"} }, friends = { {1,2,3},{},{},{} }, id = 0, level = 2;auto res = Solution().watchedVideosByFriends(watchedVideos, friends, id, level);AssertEx(vector<string>{}, res);}TEST_METHOD(TestMethod2){watchedVideos = { {"A"},{"B"},{"C"},{"D"} }, friends = { {1},{2},{3},{} }, id = 0, level = 2;auto res = Solution().watchedVideosByFriends(watchedVideos, friends, id, level);AssertEx(vector<string>{"C"}, res);}TEST_METHOD(TestMethod3){watchedVideos = { {"A","B"},{"A"},{"B"},{"A"} }, friends = { {1,2,3},{},{},{} }, id = 0, level = 1;auto res = Solution().watchedVideosByFriends(watchedVideos, friends, id, level);AssertEx(vector<string>{"B","A"}, res);}TEST_METHOD(TestMethod4){watchedVideos = { {"A","B"},{"A"},{"B"},{"B"} }, friends = { {1,2,3},{},{},{} }, id = 0, level = 1;auto res = Solution().watchedVideosByFriends(watchedVideos, friends, id, level);AssertEx(vector<string>{"A", "B"}, res);}TEST_METHOD(TestMethod5){watchedVideos = { {"A","B"},{"A"},{"B"},{"C"} }, friends = { {1,2,3},{},{},{} }, id = 0, level = 1;auto res = Solution().watchedVideosByFriends(watchedVideos, friends, id, level);AssertEx(vector<string>{"A", "B","C"}, res);}TEST_METHOD(TestMethod6){watchedVideos = { {"A","B"},{"A"},{"C"},{"B"} }, friends = { {1,2,3},{},{},{} }, id = 0, level = 1;auto res = Solution().watchedVideosByFriends(watchedVideos, friends, id, level);AssertEx(vector<string>{"A", "B", "C"}, res);}TEST_METHOD(TestMethod11){watchedVideos = { {"A","B"},{"C"},{"B","C"},{"D"} }, friends = { {1,2},{0,3},{0,3},{1,2} }, id = 0, level = 1;auto res = Solution().watchedVideosByFriends(watchedVideos, friends, id, level);AssertEx(vector<string>{"B", "C"}, res);}TEST_METHOD(TestMethod12){watchedVideos = { {"A","B"},{"C"},{"B","C"},{"D"} }, friends = { {1,2},{0,3},{0,3},{1,2} }, id = 0, level = 2;auto res = Solution().watchedVideosByFriends(watchedVideos, friends, id, level);AssertEx(vector<string>{"D"}, res);}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。