LeetCode 1311. Get Watched Videos by Your Friends

链接: https://leetcode-cn.com/problems/get-watched-videos-by-your-friends/
难度:medium

解题思路:广搜找到对应level的所有朋友,然后累加相应的video,最后排序。go语言没有啥priority queue,图简单这里排序用的直接插入排序,有点挫

Golang的数据结构支持太少了,各种都要自己写,真是麻烦。。

func watchedVideosByFriends(watchedVideos [][]string, friends [][]int, id int, level int) []string {
    visited := map[int]int{}
    queue := []Person {Person{id, 0}}
    visited[id] = 1
    for len(queue) > 0 {
        friend := queue[0]
        if friend.level == level {
            break
        }
        queue = queue[1:]

        for _, f := range friends[friend.id] {
            if visited[f] == 0 {
                queue = append(queue, Person{f, friend.level + 1})
                visited[f] = 1
            }
        }

        visited[friend.id] = 1
    }

    visited = map[int]int{}
    dict := map[string]int {}
    for _, p := range queue {
        if visited[p.id] == 1 {
            continue
        }
        for _, video := range watchedVideos[p.id] {
            dict = dict + 1
        }
        visited[p.id] = 1
    }

    result := []string {}
    for k, v := range dict {
        inserted := false
        for idx, e := range result {
            if v < dict[e] || (v == dict[e] && k < e) {
                result = append(result, "")
                copy(result[idx + 1:], result[idx:])
                result[idx] = k
                inserted = true
                break
            }
        }
        if !inserted {
            result = append(result, k)
        }
    }
    return result

}

type Person struct {
    id int
    level int
}

执行用时 : 1276 ms , 在所有 Go 提交中击败了 7.14% 的用户
内存消耗 : 6.6 MB , 在所有 Go 提交中击败了 100.00% 的用户


发表评论

您的电子邮箱地址不会被公开。