本文共 2905 字，大约阅读时间需要 9 分钟。

1. 问题描述：

有 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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/get-watched-videos-by-your-friends

2. 思路分析：

① 首先需要理解清楚题目，根据题目分析可以找到需要三个步骤来解决这个问题，第一个是需要找到当前id的level k的所有好友，这个是可以使用广度优先搜索，也即bfs来实现的，bfs需要借助于队列来实现，使用一个变量来记录当前bfs搜索的层数是多少了，我们只需要在循环中执行level - 1次即可，这样在队列中最后得到的就是id的level k的好友，在bfs搜索的过程中，需要使用set来去重，因为从题目中给出的好友是相互的形式，所以当set中没有当前的id的时候才将好友加入进队列与set中

② 第二步是遍历队列中的level k的好友，将好友观看的电影记录到map中，其中map中可以记录观看电影出现的频数，最后则需要对map中的键值对进行排序，在领扣的题解中看到可以使用java中的优先队列进行排序，使用优先队列可以自定义键值对的排序规则，这样的话就会很方便了

③ 所以这道题目本质上考察的是map、set与排序

3. 代码如下：

class Solution {    public  List
   
     watchedVideosByFriends(List
    
     
      > watchedVideos, int[][] friends, int id, int level) {        Queue
      
        queue = new LinkedList<>();        Set
       
         set = new HashSet<>();        queue.add(id);        /*用来标记哪些朋友是已经被访问了*/        set.add(id);        int curlevel = 0;        List
        
          res = new ArrayList<>(); /*统计自己看过的电影*/ if (level == 0){ for (List
         
           cur : watchedVideos){ for (int i = 0; i < cur.size(); ++i) res.add(cur.get(i)); } return res; } while (curlevel < level){ int len = queue.size(); for (int i = 0; i < len; ++i){ int curid = queue.poll(); for (int t : friends[curid]){ if (!set.contains(t)){ queue.add(t); set.add(t); } } } ++curlevel; } /*使用map来统计视频出现的频率*/ Map
          
            map = new HashMap<>(); /*队列中的最后一个元素为level k的好友*/ while (!queue.isEmpty()){ int curid = queue.poll(); List
           
             list = watchedVideos.get(curid); for (int i = 0; i < list.size(); ++i){ map.put(list.get(i), map.getOrDefault(list.get(i), 0) + 1); } } /*对map进行排序: 这里使用到了一个优先队列*/ PriorityQueue
            
             
              > priorityQueue = new PriorityQueue<>((t1, t2) -> { if (t1.getValue().equals(t2.getValue())) { return t1.getKey().compareTo(t2.getKey()); } else { return t1.getValue().compareTo(t2.getValue()); } }); map.forEach((key, value) -> priorityQueue.add(new Pair<>(key, value))); while (!priorityQueue.isEmpty()) { res.add(priorityQueue.poll().getKey()); } return res; }}
             
            
           
          
         
        
       
      
     
    
   

 

转载地址：http://spgr.baihongyu.com/