leetcode_355

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:]...)
            }
        }
    }
}

有疑问加站长微信联系（非本文作者）