X

LEETCODE 1311. Get Watched Videos by Your Friends 解题思路分析

题目大意:

获取你好友已观看的视频

有 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1311

解题思路分析:

本题的考点还真不少,解题时大概需要以下三个步骤:

  1. 首先要确定与自己相隔level层的好友有哪些。题目给出的friends数组实际上是一个图形结构,在已知起始节点(自己的id)的情况下,求距离自己为level的所有节点时,可用bfs广度优先搜索方法搞定。
  2. 获得距离自己level的所有朋友列表之后,我们遍历每个朋友的观看视频列表,统计每个视频被观看的次数,将结果保存在一个Map中,map的key为视频名称,value为被观看的次数。
  3. 给map中的元素排序,排序规则为:优先按照升序排序观看次数(value),在观看次数相同的情况下,按字典升序排列视频名称(key)。排序完成之后,将排序过的map中的视频名称(key)输出到返回结果list中即可。

实现代码:

public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
    // 第一步,bfs寻找距离自己为level的朋友列表
    Queue<Integer> q = new LinkedList<>();
    boolean[] visited = new boolean[watchedVideos.size()];
    visited[id]=true;
    q.offer(id);
    int l=0;
    while(q.size()>0){
        int size= q.size();
        while(size-->0){
            int i = q.poll();
            for(int f : friends[i]){
                if(!visited[f]){
                    visited[f]=true;
                    q.offer(f);
                }
            }
        }
        if(++l==level) break;
    }
    // 第二步,遍历朋友列表,统计他们观看过视频的次数,存入map
    Map<String, Integer> map =new HashMap<>();
    while(q.size()>0){
        for(String v : watchedVideos.get(q.poll())){
            int count = map.getOrDefault(v, 0);
            map.put(v, count+1);
        }
    }
    // 第三步,排序map
    List<Map.Entry<String, Integer>> datas=new ArrayList<>(map.entrySet());
    Collections.sort(datas,
                    (o1, o2)-> o1.getValue()==o2.getValue()?
                     o1.getKey().compareTo(o2.getKey()):o1.getValue()-o2.getValue());
    List<String> res = new ArrayList<>();
    for(Map.Entry<String, Integer> e : datas){
        res.add(e.getKey());
    }
    return res;
}

本题解法执行时间为28ms。

Runtime: 28 ms, faster than 66.10% of Java online submissions for Get Watched Videos by Your Friends.

Memory Usage: 40 MB, less than 100.00% of Java online submissions for Get Watched Videos by Your Friends.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1311-get-watched-videos-by-your-friends-解题思路分析/
Categories: leetcode
kwantong: