Leetcode 1311:获取你好友已观看的视频(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1311:获取你好友已观看的视频(超详细的解法!!!)

in leetcode with 0 comment

n 个人,每个人都有一个 0n-1 的唯一 id

给你数组 watchedVideosfriends ,其中 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 。

提示:

解题思路

我们观察题目不难发现问题中的friends构成了一个图,而问题就是在问题从id出发采用bfs遍历图的话,就是图的level层数对应的watchedVideos

我们这里的队列中存储了当前节点的id层级,如果当前层级是level,只需将该层的所有元素添加队列。然后遍历队列里面的所元素,统计watchedVideos对应的出现次数即可。

最后还需注意排序的问题,需要使用出现次数作为第一优先级,字典序作为第二优先级。

class Solution:
    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
        q, cnt = [[id, 0]], collections.defaultdict(int)
        seen = {id}
        while q:
            n = len(q)
            for _ in range(n):
                idx, le = q.pop(0)
                for i in friends[idx]:
                    if i not in seen:
                        q.append([i, le + 1])
                        seen.add(i)

            if le == level - 1:
                break
                
        for idx, _ in q:
            for c in watchedVideos[idx]:
                cnt[c] += 1
        return sorted(cnt, key=lambda x:(cnt[x], x))

更加简洁的写法:

class Solution:
    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
        q, seen = [id], {id}
        for _ in range(level):
            n = len(q)
            for _ in range(n):
                idx = q.pop(0)
                for i in friends[idx]:
                    if i not in seen:
                        q.append(i)
                        seen.add(i)
        
        cnt = collections.Counter([c for idx in q for c in watchedVideos[idx]])
        return sorted(cnt, key=lambda x:(cnt[x], x))        

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses