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

CSDN 2024-07-24 13:35:01 阅读 97

本文涉及知识点

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

代码

核心代码

<code>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;