LeetCode-1311. Get Watched Videos by Your Friends

LeetCode-1311. Get Watched Videos by Your Friends

There are ​​n​​ people, each person has a unique id between ​​0​​​ and ​​n-1​​​. Given the arrays ​​watchedVideos​​​ and ​​friends​​​, where ​​watchedVideos[i]​​​ and ​​friends[i]​​​ contain the list of watched videos and the list of friends respectively for the person with ​​id = i​​.

Level 1 of videos are all watched videos by your friends, level 2 of videos are all watched videos by the friends of your friends and so on. In general, the level k of videos are all watched videos by people with the shortest path equal to k with you. Given your ​​id​​​ and the ​​level​​ of videos, return the list of videos ordered by their frequencies (increasing). For videos with the same frequency order them alphabetically from least to greatest.

Example 1:

Input: watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1Output: ["B","C"] Explanation: You have id = 0 (green color in the figure) and your friends are (yellow color in the figure):Person with id = 1 -> watchedVideos = ["C"] Person with id = 2 -> watchedVideos = ["B","C"] The frequencies of watchedVideos by your friends are: B -> 1 C -> 2

Example 2:

Input: watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2Output: ["D"]Explanation: You have id = 0 (green color in the figure) and the only friend of your friends is the person with id = 3 (yellow color in the figure).

Constraints:

​​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​​if​​friends[i]​​​ contains​​j​​​, then​​friends[j]​​​ contains​​i​​

题解：

class Solution {public: static bool cmp (pair a, pair b) { if (a.second != b.second) { return a.second < b.second; } return a.first < b.first; } vector watchedVideosByFriends(vector>& watchedVideos, vector>& friends, int id, int level) { queue q; q.push(id); vector res; unordered_map mp; vector visit(friends.size(), false); visit[id] = true; while (q.empty() == false) { if (level == 0) { while (q.empty() == false) { int cur = q.front(); q.pop(); for (int j = 0; j < watchedVideos[cur].size(); j++) { mp[watchedVideos[cur][j]]++; } } } else { int cnt = q.size(); for (int t = 0; t < cnt; t++) { int cur = q.front(); q.pop(); for (int i = 0; i < friends[cur].size(); i++) { if (visit[friends[cur][i]] == false) { q.push(friends[cur][i]); visit[friends[cur][i]] = true; } } } level--; } } vector> vec(mp.begin(), mp.end()); sort(vec.begin(), vec.end(), cmp); for (int i = 0; i < vec.size(); i++) { res.push_back(vec[i].first); } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。