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，用戶idint 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

總結

以上是生活随笔為你收集整理的LeetCode 355. 设计推特（哈希map+set）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。