# LeetCode: 1311. 获取你好友已观看的视频¶

## 1、题目描述¶

n 个人，每个人都有一个 0n-1 的唯一 id 。给你数组 watchedVideosfriends ，其中 watchedVideos[i]friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。

Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看过的视频，以此类推。一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好友观看过的视频。

输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1

id 为 1 -> watchedVideos = ["C"]
id 为 2 -> watchedVideos = ["B","C"]

B -> 1
C -> 2


输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2



• 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

## 2、解题思路¶

• 广度优先搜索
from collections import defaultdict

class Solution:
def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
if level == 0:
return sorted(watchedVideos[id])

length = len(watchedVideos)
visited = [0] * length

d = [id]
visited[id] = 1
videos = defaultdict(int)
while level > 0:
next_level = []
for friend in d:
for next_friend in friends[friend]:

if not visited[next_friend]:
next_level.append(next_friend)
if level == 1:
for video in watchedVideos[next_friend]:
videos[video] += 1
visited[next_friend] = 1
level -= 1
d = next_level
ans = []
for v in sorted(videos.items(), key=lambda x: [x[1], x[0]]):
ans.append(v[0])
return ans