[LeetCode] 1311. Get Watched Videos by Your Friends #1311

grandyang · 2019-05-30T16:34:31Z

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 exactly 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 = 1
Output: ["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 = 2
Output: ["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

这道题说是有n个人，编号为0到 n-1，给了两个数组 watchedVideos 和 friends，分别表示第i个人看过的电影，和第i个人的所有朋友。现在给了个编号 id，和层数 level，让找出该人的第 level 层好友看过的所有电影，按频率由低到高排序，频率相同的按照字母顺序从小到大排序。题目比较长，好在给了例子，并且还有示意图可以帮助理解，这里首先要理解第 level 层好友指的是什么，用过领英 Linkedin 的都知道，好友后面会显示 1st，表示第一层好友，而好友的好友，会显示 2nd，以此类推，领英一般只显示到 3rd。

这里也可以理解成二叉树中两个结点之间的距离，于是问题实际上就转变成了找出图中距离给定结点 level 个位置所有结点，即本题中的第 level 层的所有好友，然后根据 watchedVideos 数组就可以找到所有好友的电影了。找第 level 层的结点使用层序遍历比较简单，这里借助一个 queue 来实现，先把给定的 id 加入到 queue 中，还需要一个访问数组 visited 来记录所有访问过的结点，将 id 位置标记为已访问。用数组 ids 来记录所有和给定结点距离为 level 的结点，接下来进行广度优先遍历 Breadth-first search，条件是 queue 不为空，且 level 大于等于0，我们并不需要遍历完所有层，而是只要遍历 level 层即可。

在 while 循环中，记得要用层序遍历的写法，里面套一个 for 循环，注意使用了从 q.size() 遍历到0的小技巧，避免了 queue 大小变化的问题。在 for 循环中，取出队首结点，判断若此时 level 等于0了，说明当前结点是要求的目标结点，加入到 ids 数组。接下来遍历和当前结点相连的所有结点，若已经访问过了，直接跳过，否则标记为已访问，然后将新结点加入到 queue 中，for 循环结束后，level 要自减1。这样我们就找到了和目标结点相距为 level 的所有结点，接下来要统计这些人看过的所有电影，使用 HashMap 来建立电影和其出现次数之间的映射，通过 watchedVideos 来快速统计电影和其出现次数。题目中对返回的电影有排序要求，这里可以使用一个 TreeSet，利用其自动排序的特点，里面放次数和电影名称的 pair 对儿，最后将电影名称按顺序取出来放到结果 res 数组中即可，参见代码如下：

class Solution {
public:
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        int n = watchedVideos.size();
        vector<string> res;
        unordered_map<string, int> videoCnt;
        set<pair<int, string>> videoSet;
        vector<int> ids, visited(n);
        queue<int> q{{id}};
        visited[id] = 1;
        while (!q.empty() && level >= 0) {
            for (int i = q.size(); i > 0; --i) {
                int t = q.front(); q.pop();
                if (level == 0) ids.push_back(t);
                for (int j : friends[t]) {
                    if (visited[j]) continue;
                    visited[j] = 1;
                    q.push(j);
                }
            }
            --level;
        }
        for (int id : ids) {
            for (string video : watchedVideos[id]) {
                ++videoCnt[video];
            }
        }
        for (auto &a : videoCnt) {
            videoSet.insert({a.second, a.first});
        }
        for (auto &p : videoSet) {
            res.push_back(p.second);
        }
        return res;
    }
};

Github 同步地址:

#1311

参考资料：

https://leetcode.com/problems/get-watched-videos-by-your-friends/

https://leetcode.com/problems/get-watched-videos-by-your-friends/discuss/470695/C%2B%2B-BFS-%2B-Sort

https://leetcode.com/problems/get-watched-videos-by-your-friends/discuss/470748/BFS-%2B-Hash-Map-%2B-Set

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~