我要评论本文涉及知识点
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学院，听白银讲师（也就是鄙人）的讲解。
如何你想快速形成战斗了，为老板分忧，请学习c#入职培训、c++入职培训等课程
测试环境
操作系统：win7 开发环境： vs2019 c++17
或者 操作系统：win10 开发环境： vs2022 c++17
如无特殊说明，本算法用**c++**实现。
发表评论