本文涉及知识点

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出重。

代码

核心代码

classSolution{ public:vector<string>watchedVideosByFriends(vector<vector<string>>&watchedVideos,vector<vector<int>>&friends,intid,intlevel){ constintN =watchedVideos.size();vector<vector<int>>leves ={ { id}};vector<bool>vis(N);vis[id]=true;for(inti =0;i <leves.size();i++){ vector<int>nexts;for(constauto&cur :leves[i]){ for(constauto&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(constauto&i :leves[level]){ for(constauto&s :watchedVideos[i]){ mVideoCnt[s]++;}}set<pair<int,string>>sCntVideo;for(constauto&[s,cnt]:mVideoCnt){ sCntVideo.emplace(cnt,s);}vector<string>ret;for(constauto&[tmp,s]:sCntVideo){ ret.emplace_back(s);}returnret;}};

单元测试

vector<vector<string>>watchedVideos;vector<vector<int>>friends;intid,level;TEST_METHOD(TestMethod1){ watchedVideos ={ { "A","B"},{ "C"},{ "B","C"},{ "D"}},friends ={ { 1,2,3},{ },{ },{ }},id =0,level =2;autores =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;autores =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;autores =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;autores =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;autores =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;autores =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;autores =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;autores =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++**实现。