LeetCode 355. 設計推特（哈希map+set）

1. 題目

設計一個簡化版的推特(Twitter)，可以讓使用者實作發送推文，關注/取消關注其他使用者，能夠看見關注人（包括自己）的最近十條推文。你的設計需要支援以下的幾個功能：

• postTweet(userId, tweetId)

  : 建立一條新的推文

• getNewsFeed(userId)

  : 檢索最近的十條推文。每個推文都必須是由此使用者關注的人或者是使用者自己發出的。推文必須按照時間順序由最近的開始排序。

• follow(followerId, followeeId)

  : 關注一個使用者

• unfollow(followerId, followeeId)

  : 取消關注一個使用者

示例:

Twitter twitter = new Twitter();

// 使用者1發送了一條新推文 (使用者id = 1, 推文id = 5).
twitter.postTweet(1, 5);

// 使用者1的擷取推文應當傳回一個清單，其中包含一個id為5的推文.
twitter.getNewsFeed(1);

// 使用者1關注了使用者2.
twitter.follow(1, 2);

// 使用者2發送了一個新推文 (推文id = 6).
twitter.postTweet(2, 6);

// 使用者1的擷取推文應當傳回一個清單，其中包含兩個推文，id分别為 -> [6, 5].
// 推文id6應當在推文id5之前，因為它是在5之後發送的.
twitter.getNewsFeed(1);

// 使用者1取消關注了使用者2.
twitter.unfollow(1, 2);

// 使用者1的擷取推文應當傳回一個清單，其中包含一個id為5的推文.
// 因為使用者1已經不再關注使用者2.
twitter.getNewsFeed(1);           

複制

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/design-twitter

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

struct cmp
{
    bool operator()(const vector<int> &a, const vector<int> &b) const
    {
        return a[0] < b[0];
    }
};
class Twitter {
    unordered_map<int,unordered_set<int>> m;//id，關注的人
    set<vector<int>,cmp> tweet;//time, 推文id，使用者id
    int time = 0;
    int count;
    vector<int> ans;
public:
    /** Initialize your data structure here. */
    Twitter() {}
    
    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        tweet.insert({time++, tweetId, 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. */
    vector<int> getNewsFeed(int userId) {
        count = 10;
        ans.clear();
        for(auto it = tweet.rbegin(); it != tweet.rend() && count; ++it)
        {
            if((*it)[2]==userId || m[userId].count((*it)[2]))
            {
                ans.push_back((*it)[1]);
                count--;
            }
        }
        return ans;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        m[followerId].insert(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        m[followerId].erase(followeeId);
    }
};           

複制

532 ms 21.7 MB