题目来源

• leetcode：355. 设计推特

题目描述

class Twitter {
    
public:
    Twitter() {
    

    }
    
    void postTweet(int userId, int tweetId) {
    

    }
    
    vector<int> getNewsFeed(int userId) {
    

    }
    
    void follow(int followerId, int followeeId) {
    

    }
    
    void unfollow(int followerId, int followeeId) {
    

    }
};

题目解析

实现一

思路

• 道题的主要难点在于实现 getNewsFeed() 函数，这个函数获取自己和好友的最近 10 条消息
• 需要两个映射：
  • 映射：key = userId， value为当前用户关注的其他所有用户的ID的集合
    • 这里只需要保证加入的用户ID唯一就可以了，可以用unordered_set来做
  • 映射：key = userId， value为当前用户发送的所有博文
    • 要想获得最近的消息，我们需要知道博文的时间发送先后顺序
    • 因为tweetId不确定是不是自增的，所以我们定义一个cnt来模拟时间点，每发送一个消息，time就自增1，就知道哪个博文是先发的了
    • 怎么将tweetId和cnt绑定起来呢？
      • 我们可以定义一个结构体，也可以定义一个map(因为是一对一的)，其key为time，value为对应tweetId。
      • 为什么要key为time呢？
        • 这样就会先根据time排序，如果time相等，就会根据tweetid排序
• 如何获取最近的10条消息呢？
  • 维护一个大小为10的哈希表
  • 然后遍历自己的好友，以及好友的所有消息（注意，先自己关注自己）
  • 如果新遍历到的消息比map中最早的消息要晚，那么将这个消息加入，然后删除最早的那个消息（这里需要有序，所以用map而不是unordered_map）

class Twitter {
    
public:
    Twitter() {
    
        time = 0;
    }
    
    void postTweet(int userId, int tweetId) {
    
        follow(userId, userId);
        tweets[userId].insert({
    time++, tweetId});
    }
    
    vector<int> getNewsFeed(int userId) {
    
        vector<int> res;
        map<int, int> top10;
        for (auto id : friends[userId]) {
    
            for (auto a : tweets[id]) {
    
                top10.insert({
    a.first, a.second});
                if (top10.size() > 10) top10.erase(top10.begin());
            }
        }
        for (auto a : top10) {
    
            res.insert(res.begin(), a.second);
        }
        return res;
    }
    
    void follow(int followerId, int followeeId) {
    
        friends[followerId].insert(followeeId);
    }
    
    void unfollow(int followerId, int followeeId) {
    
        if (followerId != followeeId) {
    
            friends[followerId].erase(followeeId);
        }
    }
    
private:
    int time;
    unordered_map<int, unordered_set<int>> friends;
    unordered_map<int, map<int, int>> tweets;
};

下面这种方法和上面的基本一样，就是在保存用户所有消息的时候，用的是 vector<pair<int, int>>，这样可以用 priority_queue 来帮助找出最新 10 条消息

class Twitter {
    
    int time;
    std::unordered_map<int, std::unordered_set<int>> friends;
    std::unordered_map<int, std::vector<std::pair<int, int>>> tweets;
public:
    Twitter() {
    
        time = 0;
    }
    void postTweet(int userId, int tweetId) {
    
        follow(userId, userId);
        tweets[userId].push_back({
    ++time, tweetId});
    }

    vector<int> getNewsFeed(int userId) {
    
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> minPQ;
        for(auto id : friends[userId]){
    
            for(auto a : tweets[id]){
    
                minPQ.push(a);
                if (minPQ.size() > 10) minPQ.pop();
            }
        }
        
        std::vector<int> vec;
        while (!minPQ.empty()){
    
            vec.insert(vec.begin(), minPQ.top().second);
            minPQ.pop();
        }
        return vec;
    }

    void follow(int followerId, int followeeId) {
    
        friends[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
    
        if(followeeId != followerId){
    
            friends[followerId].erase(followeeId);
        }
    }
};

实现二：哈希表 + 链表 + 优先队列

类似题目

• leetcode：23. 合并K个升序链表