【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;
			}
		};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

单元测试

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);
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

扩展阅读

视频课程

先学简单的课程，请移步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++**实现。