分享
LeetCode 1311. Get Watched Videos by Your Friends
码农老姜 · · 1259 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
链接: 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[video] = dict[video] + 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% 的用户
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1259 次点击
上一篇:阿里云运维架构实践秘籍
下一篇:Golang Tips
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
链接: 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[video] = dict[video] + 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% 的用户