leetcode_355

淳属虚构 · · 375 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Golang:

思路:设计推特,搬运我的题解

这里的代码依旧有着很大优化的空间,比如按时间排序上,可以维护一个堆;对于每一个用户,我们可以只保存他/她的最近十条推特
但是不太想写了,因为比较麻烦。。。
globalId:类似timestamp时间标记
follower:记录每个用户关注的用户列表
checkFollowed表示关注关系,用户A是否关注了用户B,key为“id id”的形式,应该是可以保证唯一性的
twitter存储每个用户发过的推,但是value存的是globalId,方便以后取出来
findtwitter存储的是所有用户发的推
注意,这套代码是不满足并行与分布式的要求的。。。

代码如下:

type Twitter struct {
    globalId int
    follower map[int][]int
    checkFollowed map[string]bool
    //这里twitter的value存globalId
    twitter map[int][]int
    findTwitter []int
}
/** Initialize your data structure here. */
func Constructor() Twitter {
    return Twitter{
        globalId: 0,
        follower: make(map[int][]int),
        checkFollowed: make(map[string]bool),
        twitter: make(map[int][]int),
        findTwitter: make([]int,0),
    }
}
/** Compose a new tweet. */
func (this *Twitter) PostTweet(userId int, tweetId int)  {
    this.twitter[userId]=append(this.twitter[userId],this.globalId)
    this.findTwitter=append(this.findTwitter,tweetId)
    this.globalId++
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
func (this *Twitter) GetNewsFeed(userId int) []int {
    //可以维护一个大小为10的堆,但这里不这么写了(考虑到可能没有10个推特)
    var globalId []int
    cpy:=make([]int,len(this.follower[userId]))
    copy(cpy,this.follower[userId])
    key:=strconv.Itoa(userId)+" "+strconv.Itoa(userId)
    //因为测试用例里有自己关注自己这种东西,所以加上这一句
    if !this.checkFollowed[key]{
        cpy=append(cpy,userId)
    }
    for _,v:=range cpy{
        globalId=append(globalId,this.twitter[v]...)
    }
    sort.Ints(globalId)
    var res []int
    for i:=len(globalId)-1;i>=0&&i>=len(globalId)-10;i--{
        res=append(res,this.findTwitter[globalId[i]])
    }
    return res
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Follow(followerId int, followeeId int)  {
    key:=strconv.Itoa(followerId)+" "+strconv.Itoa(followeeId)
    if !this.checkFollowed[key]{
        //关注关系更新
        this.checkFollowed[key]=true
        this.follower[followerId]=append(this.follower[followerId],followeeId)
    }

}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Unfollow(followerId int, followeeId int)  {
    key:=strconv.Itoa(followerId)+" "+strconv.Itoa(followeeId)
    if this.checkFollowed[key]{
        this.checkFollowed[key]=false
        for i:=0;i<len(this.follower[followerId]);i++{
            if this.follower[followerId][i]==followeeId{
                this.follower[followerId]=append(this.follower[followerId][:i],this.follower[followerId][i+1:]...)
            }
        }
    }
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:淳属虚构

查看原文:leetcode_355

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

375 次点击  
加入收藏 微博
上一篇:leetcode_890
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传