【C++BFS】1311. 获取你好友已观看的视频_业界新闻

发布时间:2024-08-08 02:17

阅读量:0

本文涉及知识点

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); 		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功