leetcode 设计推特

题目描述：

https://leetcode-cn.com/problems/design-twitter/

解

package main

import (
    "sort"
    "time"
)

type TwitterInfo struct {
    TwitterID   int
    TwitterTime int64
}
type Twitter struct {
    // 用户关注
    Relation map[int][]int
    // 用户feed
    Feeds map[int][]TwitterInfo
}

/** Initialize your data structure here. */
func Constructor() Twitter {
    relation := make(map[int][]int)
    feeds := make(map[int][]TwitterInfo)
    return Twitter{
        Relation: relation,
        Feeds:    feeds,
    }
}

/** Compose a new tweet. */
func (this *Twitter) PostTweet(userId int, tweetId int) {
    var tweetIds = make([]TwitterInfo, 0, len(this.Feeds[userId])+1)
    tweetIds = append(tweetIds, this.GetNewTwitterInfo(tweetId))
    this.Feeds[userId] = append(tweetIds, this.Feeds[userId]...)
}

/** 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 {
    var feeds []TwitterInfo
    if ownFeeds, ok := this.Feeds[userId]; ok && len(ownFeeds) != 0 {
        feeds = append(feeds, ownFeeds...)
    }
    if followeeId, ok := this.Relation[userId]; ok && len(followeeId) != 0 {
        for _, v := range followeeId {
            if feed, ok := this.Feeds[v]; ok {
                feeds = append(feeds, feed...)
            }

        }
    }
    sort.Slice(feeds, func(i, j int) bool {
        return feeds[i].TwitterTime > feeds[j].TwitterTime
    })
    var r []int
    var num int
    for _, v := range feeds {
        r = append(r, v.TwitterID)
        num++
        if num >= 10 {
            break
        }
    }
    return r
}

/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Follow(followerId int, followeeId int) {
    if followerId == followeeId {
        return
    }
    for _, v := range this.Relation[followerId] {
        if v == followeeId {
            return
        }
    }
    this.Relation[followerId] = append(this.Relation[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) {
    if followers, ok := this.Relation[followerId]; ok {
        var newFollow []int
        for _, v := range followers {
            if v == followeeId {
                continue
            }
            newFollow = append(newFollow, v)
        }
        this.Relation[followerId] = newFollow
    }

}

func (this *Twitter) GetNewTwitterInfo(tweetId int) TwitterInfo {
    return TwitterInfo{
        TwitterID:   tweetId,
        TwitterTime: time.Now().UnixNano(),
    }
}

/**
 * Your Twitter object will be instantiated and called as such:
 * obj := Constructor();
 * obj.PostTweet(userId,tweetId);
 * param_2 := obj.GetNewsFeed(userId);
 * obj.Follow(followerId,followeeId);
 * obj.Unfollow(followerId,followeeId);
 */

使用了两个map，map中分别存放了用户关系和用户feed，函数中使用sort.slice对时间进行了排序，当然实现方式很简单，几乎接近了暴力法，以上根据输出结果，在执行时间上还有很大的上升空间，其实就是多用点空间，换时间的做法。获取队列的时候是计算用户关注关系，实时排序而得；利用空间上，大可以为每个用户维护一个Twitter列表，里面使用活跃时间排序，最长10，每单关注关系用户或者自己发送Twitter时，更新这个列表；获取时也就可以从这里取出。
这些都是并发不安全的！

引用

https://leetcode-cn.com/problems/design-twitter/submissions/