力扣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赋给res res.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); } };
原文地址:https://blog.csdn.net/Pisasama/article/details/140602375
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!