Design Twitter 面向对象设计优先队列 HashMap

àì夳堔傛蜴生んèń 2023-11-12 00:45 139阅读 0赞

应用面向对象设计(OO)模拟Twitter的几个功能，分别是：

1.  发推postTweet(userId, tweetId): Compose a new tweet.
2.  获取最近的十条推文getNewsFeed(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.
3.  关注follow(followerId, followeeId): Follower follows a follow.
4.  取关unfollow(followerId, followeeId): Follower unfollows a followee

首先要考虑的是，这里应该有用户、推文，用户很简单，一个整形就可以表示。推文需要有，userId，tweetId，timestamp（我们这里并不需要详细的时间，只要有每条推文的先后顺数就可以了），对此我们使用struct tweet  
接下来分析功能，每一个用户都应该有一个数组来记录他的关注对象，另外一个数组纪录他的推文，这里可以选择建一个structure记录这些数据，但是在这道题里我们只用到了两个unordered\_maps存放对应数据，在map中每个整形（userId）都有对应的followees和tweets  
有了这样的数据结构呢，postTweet, follow, unfollow都很好实现了，只需要对map进行相应操作即可。  
有些难得是getNewsFeed这个函数，返回用户关注的最近十条推文，包括他自己的。对于这种有顺序的东西很容易想到[priority\_queue][priority_queue], 下面这个solution用一个priority-queue存储该用户关注的每个用户的推文的begin iterator, end iterator. begin iterator用于从每个follow发的最新的推文中选出最新的。

class Twitter {
        private:
        struct tweet {
            int userId;
            int tweetId;
            int timesStamp;
            tweet(int x, int y, int z): userId(x), tweetId(y), timesStamp(z){};
        };
        struct mycompare {
            bool operator()(pair<list<tweet>::iterator, list<tweet>::iterator> p1,
                            pair<list<tweet>::iterator, list<tweet>::iterator> p2) {
                return p1.first->timesStamp < p2.first->timesStamp;
            }
        };
        int timeLabel = 0;
        unordered_map<int, unordered_set<int>> followees;
        unordered_map<int, list<tweet>> tweets;
    public:
        /** Initialize your data structure here. */
        Twitter() {}
        
        /** Compose a new tweet. */
        void postTweet(int userId, int tweetId) {
            followees[userId].insert(userId);
            tweets[userId].push_front(tweet(userId, tweetId, timeLabel));
            timeLabel++;
        }
        
        /** 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. */
        vector<int> getNewsFeed(int userId) {
            vector<int> res;
            if (followees.find(userId) == followees.end()) return res;
            priority_queue<pair<tweet, tweet>,
                           vector<pair<tweet, tweet>>,
                           mycompare> pq;
            for (auto it = followees[userId].begin(); it != followees[userId].end(); it++)
                if (tweets[*it].begin() != tweets[*it].end())
                    pq.push(make_pair(* tweets[*it].begin(), * tweets[*it].end()));
            int index = 0;
            while(!pq.empty() && index < 10) {
                auto tmp = pq.top();
                pq.pop();
                res.push_back(tmp.first.tweetId);
                if (++tmp.first != tmp.second)
                    pq.push(tmp);
                index++;
            }
            return res;
        }
        
        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        void follow(int followerId, int followeeId) {
            followees[followerId].insert(followerId);
            followees[followerId].insert(followeeId);
        }
        
        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        void unfollow(int followerId, int followeeId) {
            if (followees.find(followerId) != followees.end() && followerId != followeeId) {
                followees[followerId].erase(followeeId);
            }
        }
    
    };
    
    /**
     * Your Twitter object will be instantiated and called as such:
     * Twitter obj = new Twitter();
     * obj.postTweet(userId,tweetId);
     * vector<int> param_2 = obj.getNewsFeed(userId);
     * obj.follow(followerId,followeeId);
     * obj.unfollow(followerId,followeeId);
     */

class Twitter \{  
private:  
unordered\_map<int,unordered\_set<int>> user;  
vector<pair<int,int>> tweet;  
public:  
/\*\* Initialize your data structure here. \*/  
Twitter() \{

/\*\* Compose a new tweet. \*/  
void postTweet(int userId, int tweetId) \{  
tweet.push\_back(make\_pair(userId,tweetId));  
\}

/\*\* Retrieve the 10 most recent tweet ids in the user's news feed. \*/  
vector<int> getNewsFeed(int userId) \{  
vector<int> ret;  
for(int i=tweet.size()-1; i>=0; --i)\{  
if(userId == tweet\[i\].first || user\[userId\].find(tweet\[i\].first) != user\[userId\].end())\{  
ret.push\_back(tweet\[i\].second);  
\}  
if((int)ret.size() == 10) break;  
\}  
return ret;  
\}

/\*\* Follower follows a followee. If the operation is invalid, it should be a no-op. \*/  
void follow(int followerId, int followeeId) \{  
user\[followerId\].insert(followeeId);  
\}

/\*\* Follower unfollows a followee. If the operation is invalid, it should be a no-op. \*/  
void unfollow(int followerId, int followeeId) \{  
user\[followerId\].erase(followeeId);  
\}  
\};

[priority_queue]: https://link.jianshu.com/?t=http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/