golang 解法, 执行用时: 80 ms, 内存消耗: 7.2 MB, 提交时间: 2023-09-23 10:56:29

// bfs
func watchedVideosByFriends(watchedVideos [][]string, friends [][]int, id int, level int) []string {
    visited := make(map[int]bool)
    videos  := make(map[string]int)
    
    queue := []int{id}
    visited[id] = true

    for len(queue) > 0 {
        level--
        length := len(queue)
        for _, i := range queue {
            for _, j := range friends[i] {
                if !visited[j] {
                    visited[j] = true
                    queue = append(queue, j)
                    if level == 0 {
                        for _, v := range watchedVideos[j] {
                            videos[v]++
                        }
                    }
                }
            }
        }
        if level == 0 {
            break
        }
        queue = queue[length:]
    }

    res := make([]string, 0, len(videos))
    for k := range videos {
        res = append(res, k)
    }

    sort.Slice(res, func(i, j int) bool {
        return videos[res[i]] < videos[res[j]] || videos[res[i]] == videos[res[j]] && res[i] < res[j]
    })

    return res
}

golang 解法, 执行用时: 64 ms, 内存消耗: 7.3 MB, 提交时间: 2023-09-23 10:56:00

func watchedVideosByFriends(watchedVideos [][]string, friends [][]int, id int, k int) []string {
    kfriend := []int{}
    queue := []int{id}
    visited := make(map[int]bool)
    visited[id] = true
    step := 0
    for len(queue)!=0{
        if step == k{
            kfriend = queue
            break
        }
        tmp := queue
        queue = nil
        for _,c:=range tmp{
            for _,f:=range friends[c]{
                if !visited[f]{
                    visited[f] = true
                    queue = append(queue,f)
                }
            }
        }
        step ++
    }
    if kfriend == nil{
        return nil
    }
    mp := make(map[string]int)
    ans :=[]string{}
    for _,f:=range kfriend{
        for _,s:=range watchedVideos[f]{
            mp[s]++
            if mp[s]==1{
                ans = append(ans,s)
            }
        }
    }
    sort.Slice(ans,func(i,j int)bool{
        if mp[ans[i]]==mp[ans[j]]{
            return ans[i]<ans[j]
        }
        return mp[ans[i]]<mp[ans[j]]
    })
    return ans
}

java 解法, 执行用时: 32 ms, 内存消耗: 44.2 MB, 提交时间: 2023-09-23 10:55:25

class Solution {
    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
        int n = friends.length;
        boolean[] visited = new boolean[n];
        Map<String, Integer> map = new HashMap<>();

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{id, 0});
        visited[id] = true;
        while (queue.size() > 0) {
            int[] poi = queue.poll();
            if (poi[1] < level) {
                for (int friend : friends[poi[0]]) {
                    if (visited[friend]) continue;
                    visited[friend] = true;
                    queue.offer(new int[]{friend, poi[1]+1});
                }
            } else {
                List<String> videos = watchedVideos.get(poi[0]);
                for (String video : videos) {
                    int count = map.getOrDefault(video, 0)+1;
                    map.put(video, count);
                }
            }
        }

        List<String> res = new ArrayList<>();
        for (String key : map.keySet()) {
            res.add(key);
        }
        res = res.stream().sorted((x, y)->{
            if (map.get(x) == map.get(y)) {
                return x.compareTo(y);
            } else {
                return map.get(x) - map.get(y);
            }
        }).collect(Collectors.toList());

        return res;
    }
}

python3 解法, 执行用时: 80 ms, 内存消耗: 18 MB, 提交时间: 2023-09-23 10:55:06

class Solution:
    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
        n = len(friends)
        used = [False] * n
        q = collections.deque([id])
        used[id] = True
        for _ in range(level):
            span = len(q)
            for i in range(span):
                u = q.popleft()
                for v in friends[u]:
                    if not used[v]:
                        q.append(v)
                        used[v] = True
        
        freq = collections.Counter()
        for _ in range(len(q)):
            u = q.pop()
            for watched in watchedVideos[u]:
                freq[watched] += 1

        videos = list(freq.items())
        videos.sort(key=lambda x: (x[1], x[0]))

        ans = [video[0] for video in videos]
        return ans

cpp 解法, 执行用时: 88 ms, 内存消耗: 36.5 MB, 提交时间: 2023-09-23 10:54:47

using PSI = pair<string, int>;

class Solution {
public:
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        int n = friends.size();
        vector<bool> used(n);
        queue<int> q;
        q.push(id);
        used[id] = true;
        // 1. 找出所有 Level k 的好友
        for (int _ = 1; _ <= level; ++_) {
            int span = q.size();
            for (int i = 0; i < span; ++i) {
                int u = q.front();
                q.pop();
                for (int v: friends[u]) {
                    if (!used[v]) {
                        q.push(v);
                        used[v] = true;
                    }
                }
            }
        }
        
        // 2. 统计好友观看过的视频
        unordered_map<string, int> freq;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const string& watched: watchedVideos[u]) {
                ++freq[watched];
            }
        }
        
        // 3. 将视频按照要求排序
        vector<PSI> videos(freq.begin(), freq.end());
        sort(videos.begin(), videos.end(), [](const PSI& p, const PSI& q) {
            return p.second < q.second || (p.second == q.second && p.first < q.first);
        });
        
        vector<string> ans;
        for (const PSI& video: videos) {
            ans.push_back(video.first);
        }
        return ans;
    }
};