355. 设计推特

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
//
// Created by 13467 on 2022/10/3.
//
/**
 * 设计推特
 */

#include <vector>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;
int timestamp = 0;
class Tweet{
public:
    Tweet* next;
    int id;
    int time;
    Tweet(int id,int time){
        this->id = id;
        this->time = time;
        this->next = nullptr;
    }
};
class User{
public:
    int id;
    unordered_set<int> followed;
    Tweet* head;
    User(int userId){
        this->id = userId;
        this->head = nullptr;
//        默认关注自己
        follow(id);
    }
//        关注用户
    void follow(int userId){
        followed.insert(userId);
    }
//        取消关注
    void unfollow(int userId){
        if (userId!= this->id){
            followed.erase(userId);
        }
    }
    void post(int tweetId){
        auto tweet = new Tweet(tweetId,timestamp);
        timestamp++;
        tweet->next = head;
        head = tweet;
    }
};

class Twitter {

public:
    int userId;
//    unordered_map<int,*User> userMap;
//    unordered_map<int,User> userMap;
    unordered_map<int,User*> userMap;

    Twitter() {

    }
    void postTweet(int userId, int tweetId) {
//        c++ unordered_map不允许有重复的key。因此，如果key存在，则count返回1，如果不存在，则count返回0.
        if (!userMap.count(userId)){
            User* newUser = new User(userId);
            userMap.insert({userId, newUser});
            //            userMap.insert(userId,*new User(userId))
        }
        auto user = userMap.find(userId);
        user->second->post(tweetId);
    }


    /** follower 关注 followee */
    void follow(int followerId, int followeeId) {
        // 若 follower 不存在，则新建
        if (!userMap.count(followerId)){
            User *newUser = new User(followerId);
            userMap.insert({followerId,newUser});
        }
        // 若 followee 不存在，则新建
        if (!userMap.count(followeeId)){
            User *newUser = new User(followeeId);
            userMap.insert({followeeId,newUser});
        }
        userMap.find(followerId)->second->follow(followeeId);
    }
    /** follower 取关 followee，如果 Id 不存在则什么都不做 */
    void unfollow(int followerId, int followeeId) {
        if (userMap.count(followerId)){
            auto follower = userMap.find(followerId);
            follower->second->unfollow(followeeId);
        }
    }

    vector<int> getNewsFeed(int userId);
};

// 重载< 运算符
bool operator < (Tweet &a, Tweet &b)
{
    return b.time > a.time;
}

std::vector<int>Twitter::getNewsFeed(int userId) {
    vector<int> res;
    if (!userMap.count(userId)){
        return res;
    }
    unordered_set<int> followersId = userMap.find(userId)->second->followed;
    priority_queue<Tweet*> pq;
    for (auto id : followersId )
    {
        auto usr = userMap.find(id)->second->head;
        if ( !usr ) continue;

        pq.push(usr);

    }


    while( !pq.empty() )
    {

        if ( res.size() == 10 ) break;
        Tweet *twt = pq.top();
        pq.pop();
        res.push_back(twt->id);

        if( twt->next )
        {
            pq.push(twt->next);
        }

    }
    return res;
}

优先级队列实现

C++ STL priority_queue容器适配器详解

无序map容器

C++ STL unordered_map容器用法详解

运算符重载支持自定义比较函数