[LintCode] Mini Twitter 迷你推特-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

[LintCode] Mini Twitter 迷你推特

简介:

Implement a simple twitter. Support the following method:

postTweet(user_id, tweet_text). Post a tweet.
getTimeline(user_id). Get the given user's most recently 10 tweets posted by himself, order by timestamp from most recent to least recent.
getNewsFeed(user_id). Get the given user's most recently 10 tweets in his news feed (posted by his friends and himself). Order by timestamp from most recent to least recent.
follow(from_user_id, to_user_id). from_user_id followed to_user_id.
unfollow(from_user_id, to_user_id). from_user_id unfollowed to to_user_id.

Example
postTweet(1, "LintCode is Good!!!")
>> 1
getNewsFeed(1)
>> [1]
getTimeline(1)
>> [1]
follow(2, 1)
getNewsFeed(2)
>> [1]
unfollow(2, 1)
getNewsFeed(2)
>> []

这道题让我们实现一个迷你推特,具有发布消息,获得时间线,新鲜事,加关注和取消关注等功能,其中获得用户的时间线是返回最新10条推特,而新鲜事是返回最新10条自己的和好友的推特,如果取消关注了,那么返回的新鲜事中就没有取消关注的好友的推特。这是一道蛮有意思的设计题,我们为了简化问题,不会真的去获取系统时间来给推特排序,而是我们使用一个变量order,每发布一条消息,order自增1,这样我们就知道order大的发布的就晚,我们新建一个结构体Node,用来给每个tweet绑定一个order,然后我们写一个从一个Node数组中返回最后10个Node的函数,和一个从Node数组中返回前10个Node的函数,然后我们还需要两个哈希表,一个用来建立每个用户和其所有好友之间的映射,另一个用来建立每个用户和其发布的所有推特之间的映射,另外我们还需要一个变量order来记录发布推特的顺序。

对于postTweet函数,我们首先利用Tweet类提供的create函数建立一个tweet,然后我们看发布者是否在users_tweets里,如果不在添加这个用户,然后将这条推特加到和其映射的数组中,最后返回tweet。

对于getTimeline函数,我们先从该用户的推特集中返回最新的10条推特,然后按时间先后顺序排序,然后再返回即可。

对于getNewsFeed函数,我们先把该用户的推特集中最新10条保存下来,然后遍历其所有的好友,将其好友的最新10条保存下来,然后整个按时间先后顺序排序,返回最新10条即可。

对于follow函数,我们将好友加入用户的好友表里。

对于unfollow函数,我们将好友从用户的好友表里删除。

class MiniTwitter {
public:
    struct Node {
        int order;
        Tweet tweet;
        Node(int o, Tweet t): order(o), tweet(t){}
    };
    
    vector<Node> getLastTen(vector<Node> t) {
        int last = 10;
        if (t.size() < 10) last = t.size();
        return vector<Node>(t.end() - last, t.end());
    }
    
    vector<Node> getFirstTen(vector<Node> t) {
        int last = 10;
        if (t.size() < 10) last = t.size();
        return vector<Node>(t.begin(), t.begin() + last);
    }
    
    MiniTwitter() {
        order = 0;
    }

    // @param user_id an integer
    // @param tweet a string
    // return a tweet
    Tweet postTweet(int user_id, string tweet_text) {
        Tweet tweet = Tweet::create(user_id, tweet_text);
        if (!users_tweets.count(user_id)) users_tweets[user_id] = {};
        ++order;
        users_tweets[user_id].push_back(Node(order, tweet));
        return tweet;
    }

    // @param user_id an integer
    // return a list of 10 new feeds recently
    // and sort by timeline
    vector<Tweet> getNewsFeed(int user_id) {
        vector<Node> t;
        if (users_tweets.count(user_id)) {
            t = getLastTen(users_tweets[user_id]);
        }
        if (friends.count(user_id)) {
            for (auto it : friends[user_id]) {
                if (users_tweets.count(it)) {
                    vector<Node> v = getLastTen(users_tweets[it]);
                    t.insert(t.end(), v.begin(), v.end());
                }
            }
        }
        sort(t.begin(), t.end(), [](const Node &a, const Node &b){return a.order > b.order;});
        vector<Tweet> res;
        t = getFirstTen(t);
        for (auto a : t) {
            res.push_back(a.tweet);
        }
        return res;
    }
        
    // @param user_id an integer
    // return a list of 10 new posts recently
    // and sort by timeline
    vector<Tweet>  getTimeline(int user_id) {
        vector<Node> t;
        if (users_tweets.count(user_id)) {
            t = getLastTen(users_tweets[user_id]);
        }
        sort(t.begin(), t.end(), [](const Node &a, const Node &b){return a.order > b.order;});
        vector<Tweet> res;
        t = getFirstTen(t);
        for (auto a : t) {
            res.push_back(a.tweet);
        }
        return res;
    }

    // @param from_user_id an integer
    // @param to_user_id an integer
    // from user_id follows to_user_id
    void follow(int from_user_id, int to_user_id) {
        friends[from_user_id].insert(to_user_id);
    }

    // @param from_user_id an integer
    // @param to_user_id an integer
    // from user_id unfollows to_user_id
    void unfollow(int from_user_id, int to_user_id) {
        friends[from_user_id].erase(to_user_id);
    }

private:
    unordered_map<int, set<int>> friends;
    unordered_map<int, vector<Node>> users_tweets;
    int order;
};

本文转自博客园Grandyang的博客,原文链接:迷你推特[LintCode] Mini Twitter ,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章
最新文章
相关文章