设计一个简化版的推特(Twitter),可以让用户实现发送推文,关注/取消关注其他用户,能够看见关注人(包括自己)的最近 10 条推文。
实现 Twitter 类:
Twitter() 初始化简易版推特对象
void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
List
void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户。
示例:
输入
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
输出
[null, null, [5], null, null, [6, 5], null, [5]]
解释
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表,其中包含一个 id 为 5 的推文
twitter.follow(1, 2); // 用户 1 关注了用户 2
twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表,其中包含两个推文,id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前,因为它是在 5 之后发送的
twitter.unfollow(1, 2); // 用户 1 取消关注了用户 2
twitter.getNewsFeed(1); // 用户 1 获取推文应当返回一个列表,其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2
设计朋友圈时间线功能 :: labuladong的算法小抄 (gitee.io)
class cmp
{
public:
bool operator()(Tweet* a,Tweet* b)
{
return a->time
}
};
priority_queue
注意:priority_queue的第三个参数只能传仿函数,不能传函数指针,sort()方法的第三个参数两种方法均可
- int global_time=0;
-
- struct Tweet//推文类(单链表结点)
- {
- int tweetId;
- int time;
- Tweet* next;
- Tweet():tweetId(0),time(0),next(nullptr) {}
- Tweet(int tweetId):tweetId(tweetId),time(global_time++),next(nullptr)//每新建一条tweet,时间就加一
- {}
- };
-
- class User//用户类
- {
- public:
- int userId;
- unordered_set<int> follows;//关注的人存在无序集合中,以O(1)的时间复杂度插入、删除
- Tweet* head;
- User():userId(0),head(nullptr) {}
- User(int userId):userId(userId),head(nullptr) //head只是一个头指针,没有设置虚拟头结点
- {
- follows.insert(userId);//初始化时自己关注下自己
- }
- void post(int tweetId)//发推
- {
- Tweet* tweet=new Tweet(tweetId);
- tweet->next=head;//头插法
- head=tweet;//head作为头指针,一直指向链表第一个结点
- }
- void follow(int userId)//关注
- {
- this->follows.insert(userId);
- }
- void unfollow(int userId)//不能取关自己,即follows里至少要存着它自己
- {
- if(userId!=this->userId)
- {
- this->follows.erase(userId);
- }
- }
- };
-
- class Twitter
- {
- private:
- unordered_map<int,User*> mapping;//
- public:
- Twitter() {}
-
- void postTweet(int userId, int tweetId)//发推
- {
- if(!mapping.count(userId))
- {
- mapping[userId]=new User(userId);
- }
- mapping[userId]->post(tweetId);
- }
-
- void follow(int followerId, int followeeId)//关注
- {
- if(!mapping.count(followerId))//关注者不存在
- {
- mapping[followerId]=new User(followerId);
- }
- if(!mapping.count(followeeId))//被关注者不存在
- {
- mapping[followeeId]=new User(followeeId);
- }
- mapping[followerId]->follow(followeeId);
- }
-
- void unfollow(int followerId, int followeeId)//当followerId不存在时,不操作
- {
- if(mapping.count(followerId))
- {
- mapping[followerId]->unfollow(followeeId);
- }
- }
- class cmp
- {
- public:
- bool operator()(Tweet* a,Tweet* b)
- {
- return a->time
time; - }
- };
- vector<int> getNewsFeed(int userId)//利用优先队列,合并k个有序(以time大小为序)链表
- {
- vector<int> res;
- //priority_queue的第三个参数只能传仿函数,不能传函数指针,sort()方法的第三个参数两种方法均可
- priority_queue
,cmp> q; - if(mapping[userId]==nullptr)//userId没有对应的User
- {
- return res;
- }
- for(int id:mapping[userId]->follows)//先将所有链表头节点插入优先队列
- {
- if(mapping[id]->head!=nullptr)//链表头结点不为空
- q.push(mapping[id]->head);
- }
- while(!q.empty())
- {
- if(res.size()==10)//最多返回10条就够了
- break;
- Tweet* node=q.top();//弹出time值最大的(最近发表的)
- int tid=node->tweetId;
- res.push_back(tid);
- q.pop();
- if(node->next!=nullptr)//将下一篇tweet插入,进行排序
- {
- q.push(node->next);
- }
- }
- return res;
- }
-
- };
-
- /**
- * Your Twitter object will be instantiated and called as such:
- * Twitter* obj = new Twitter();
- * obj->postTweet(userId,tweetId);
- * vector
param_2 = obj->getNewsFeed(userId); - * obj->follow(followerId,followeeId);
- * obj->unfollow(followerId,followeeId);
- */