题目

有 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

解法

class Solution {

    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
        Deque<Integer> queue = new LinkedList<>();
        Set<Integer> seen = new HashSet<>();
        queue.offer(id);
        seen.add(id);
        int curLevel = 0;
        
        // 求第k层的问题，使用广度遍历, 由于是无向图。使用集合保证遍历的方向性。
        while(!queue.isEmpty() && curLevel <= level){
            int size = queue.size();

            if (curLevel == level){
                return getFriendVideos(queue, watchedVideos);
            }

            for(int idx = 0;idx < size;idx++) {
                int userId = queue.poll();
                for(int friendId: friends[userId]){
                    if (seen.contains(friendId)) continue;
                    queue.offer(friendId);
                    seen.add(friendId);
                }
            }

            curLevel += 1;
        }

        //level是不对的。超出了最大深度或为负数。抛出异常。
        throw new IllegalArgumentException("level is not valid");
    }

    private List<String> getFriendVideos(Deque<Integer> friendIds, List<List<String>> watchedVideos){

        Map<String,Integer> map = new HashMap<>();
        List<String> videos = new ArrayList<>();
        Iterator<Integer> it = friendIds.iterator();

        // 遍历第k层所有好友的id，并遍历他们看得视频， 统计个数到哈希表中。
        while(it.hasNext()){
            int id = it.next();
            for(String video : watchedVideos.get(id)){
                map.put(video, map.getOrDefault(video,0) + 1);
            }
        }

        // 将所有的视频添加到map中。
        for(String video : map.keySet()){
            videos.add(video);
        }

        // 按观看频率升序返回，如果存在频率相同的视频按名字字典序从小到大排列
        Collections.sort(videos, (v1, v2) ->{
            if ( map.get(v1) - map.get(v2) == 0 ) {
                return v1.compareTo(v2);
            }
            return map.get(v1) - map.get(v2);
        });

        return videos;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现