力扣355.设计推特
力扣355.设计推特
-
设计Node类有哈希集合存关注人的Id，有链表存推文的顺序
- 一个哈希表存推文的时间
-
class Twitter {struct Node{unordered_set<int> followee;list<int> tweet;};int recentMax,time;unordered_map<int,int> tweettime;unordered_map<int,Node> user;public:Twitter() {//当前时间time = 0;//最大推文数recentMax = 10;user.clear();}void postTweet(int userId, int tweetId) { if(user[userId].tweet.size() == recentMax)user[userId].tweet.pop_back();user[userId].tweet.push_front(tweetId);tweettime[tweetId] = ++time;}vector<int> getNewsFeed(int userId) {vector<int> res;for(auto it = user[userId].tweet.begin();it != user[userId].tweet.end();it++)res.emplace_back(*it);//遍历每个关注人 合并链表for(int followeeId : user[userId].followee){if(followeeId == userId) continue;vector<int> ans;auto it = user[followeeId].tweet.begin();int i = 0;while(i<(int)res.size() && it != user[followeeId].tweet.end()){if(tweettime[(*it)] > tweettime[res[i]]){ans.emplace_back(*it);it++;}else{ans.emplace_back(res[i]);i++;}if((int)ans.size() == recentMax) break;}//如果数量不够 并且res还有剩余for(;i<(int)res.size() && (int)ans.size() < recentMax;i++)ans.emplace_back(res[i]);//如果数量不够 并且关注人还有剩余for(;it != user[followeeId].tweet.end() && (int)ans.size() < recentMax;it++)ans.emplace_back(*it);//ans赋给resres.assign(ans.begin(),ans.end());}return res;}void follow(int followerId, int followeeId) {user[followerId].followee.insert(followeeId);}void unfollow(int followerId, int followeeId) {user[followerId].followee.erase(followeeId);}};