Self explanatory 59ms c++ solution


  • 0
    J

    The code is below, I use a Person class to represents each users' tweets and followers.

    typedef pair<int,int> oneTweet; // time, tweetId
    typedef vector<oneTweet> oneFeed; // tweets

    class Person {
    public:

    set<Person*> follow;
    
    void addFeed(int priority,int tweetId){
        feed.push_front(make_pair(priority,tweetId));
        if(feed.size() == 11){
            feed.pop_back();
        }
    }
    
    oneFeed getFeed(){
        oneFeed res(feed.begin(),feed.end());
        return res;
    }
    
    vector<int> getSortedFeed(vector<oneFeed> feeds){
        oneFeed allFeed;
        // Add its own feeds
        allFeed.insert(allFeed.end(),feed.begin(),feed.end());
        // Add followers' feeds
        for(int i = 0; i < feeds.size(); i++){
            allFeed.insert(allFeed.end(),feeds[i].begin(),feeds[i].end());
        }
        sort(allFeed.begin(),allFeed.end());
        reverse(allFeed.begin(),allFeed.end()); // the later it is, the higher the priority
        // return the latest 10
        vector<int> res;
        int size = min(10,int(allFeed.size()));
        for(int i = 0; i < size; i++){
            res.push_back(allFeed[i].second);
        }
        return res;
    }
    

    private:
    deque<pair<int,int>> feed;
    };

    class Twitter {
    public:

    unordered_map<int,Person> users;
    int time;
    
    Twitter():time(0) {
    }
    
    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        users[userId].addFeed(time++,tweetId);
    }
    
    /** 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<oneFeed> allFeed;
        set<Person*> follow = users[userId].follow;
        for(set<Person*>::iterator it = follow.begin(); it!=follow.end(); it++){
            allFeed.push_back((*it)->getFeed());
        }
        return users[userId].getSortedFeed(allFeed);
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        if(followerId == followeeId) return;
        users[followerId].follow.insert(&(users[followeeId]));
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        if((users.count(followerId) == 0)||(users.count(followeeId) == 0)) return;
        users[followerId].follow.erase(&(users[followeeId]));
    }};

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.