Leetcode 355.设计推特【C++】

地址：https://leetcode-cn.com/problems/design-twitter/

题目

设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：

1. postTweet(userId, tweetId): 创建一条新的推文
2. getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
3. follow(followerId, followeeId): 关注一个用户
4. unfollow(followerId, followeeId): 取消关注一个用户

示例：

Twitter twitter = new Twitter();

// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
twitter.postTweet(1, 5);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
twitter.getNewsFeed(1);

// 用户1关注了用户2.
twitter.follow(1, 2);

// 用户2发送了一个新推文 (推文id = 6).
twitter.postTweet(2, 6);

// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].
// 推文id6应当在推文id5之前，因为它是在5之后发送的.
twitter.getNewsFeed(1);

// 用户1取消关注了用户2.
twitter.unfollow(1, 2);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
// 因为用户1已经不再关注用户2.
twitter.getNewsFeed(1);

解题思路

首先，我写了一个多小时写出来，但是超时了，很尴尬~

还是留下我的解题思路。

根据题目要求，我们知道要保存每一条推文及其发布者，定义了一个 vector<pair<int, int>> 类型的数组 tweets 用于存储成对的 userID 和 tweetID，并且题目要求检索最近的10条推文，所以发布的时候我们就顺序存储每一条推文，这样避免了每次检索都要对推文进行排序；另外还需要对应每一个用户要存储该用户所关注的用户，考虑每一个用户关注的用户ID都是唯一的，所以我选择用集合来存储每一个用户关注的用户，定义了一个 vector<pair<int, set<int>>> 类型的数组 users ，存储所有用户的用户ID及其对应的关注的用户的集合。

（1）发推

首先直接将需要发布的推文及其发布者加入到 tweets 的末尾，然后判断发布该推文的用户是否已存在与用户数组 users ，如果已存在则不做处理，否则将该用户加入到用户数组。

（2）检索最近10条推文

判断传入的用户ID是否存在，若不存在该ID的用户，则直接返回空数组。

否则从后往前遍历推文数组 tweets ，定义一个整型 count 用于计数已找到的符合要求的推文数量，遍历结束的条件即已检索到的推文数量 count 达到10条或者已遍历完整个推文数组。对遍历到的每一个推文，判断其对应的发布者ID是否就是要检索的用户ID或者该用户所关注的某个用户的ID，若是，将该推文加入返回数组，count++ ，否则继续遍历。

（3）关注

遍历用户数组查找该用户，如果找到，则将其要关注的用户加入到关注的用户集合种；否则先将该用户加入到用户数组，再将要关注的用户ID加入到关注的用户集合。

（4）取关

遍历用户数组查找该用户，若找到，则将要取关的用户从关注的用户集合中删除，同时结束函数。

# 优化

优化这部分是后面改过的，虽然还是很耗时并且内存消耗也大，不过好歹通过了。

• 执行用时 :1648 ms, 在所有 C++ 提交中击败了5.15%的用户
• 内存消耗 :189.6 MB, 在所有 C++ 提交中击败了16.67%的用户

其实就是最开始的代码在索引的那一部分，我首先遍历了一次用户数组判断该用户是否存在，如果不存在，函数直接结束了那倒没什么影响。但如果存在的话，后续对每一条推文，我都还要再遍历一次去找这个用户，如果遍历了 n 条推文，那么就会做 n + 1 次完全重复的遍历查找，显然这是没有必要的。

所有我将判断该用户是否存在的标志改为了整型 index 并初始化为 -1 ，即表示该用户不存在，如果找到了该用户，则将 index 修改为该用户在用户数组中的位置，后续就不再需要遍历用户数组去查找该用户了。

我将优化部分的代码放到了👇🏻最后面👇🏻

代码（超时）

原始代码（未优化）

class Twitter {
    vector<pair<int, int>> tweets;//所有推文
    vector<pair<int, set<int>>> users;//所有用户及其关注的用户
public:
    /** Initialize your data structure here. */
    Twitter() {

    }

    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        //加入推文数组
        tweets.push_back({ userId,tweetId });
        //判断该用户是否存在
        for (auto user : users) {
            if (user.first == userId) {
                return;//如果用户存在，函数将在这里结束
            }
        }
        //函数执行到这里说明用户不存在，将用户加入到用户列表
        users.push_back({ userId,{} });
    }

    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    vector<int> getNewsFeed(int userId) {
        vector<int> ans;
        //判断是否存在该id的用户
        bool exist = false;
        for (auto user : users) {
            if (userId == user.first) {
                exist = true;
                break;
            }
        }
        //不存在直接返回空数组
        if (exist == false) {
            return ans;
        }
        int amount = tweets.size();
        int count = 0;
        for (int i = 0; count < 10 && i < tweets.size(); i++) {
            if (tweets[amount - i - 1].first == userId || isFollowing(userId, tweets[amount - i - 1].first)) {
                ans.push_back(tweets[amount - i - 1].second);
                count++;
            }
        }
        return ans;
    }

    // id1是否关注了id2
    bool isFollowing(int id1, int id2) {
        for (int i = 0; i < users.size(); i++) {
            if (users[i].first == id1 && users[i].second.find(id2) != users[i].second.end()) {
                return true;
            }
        }
        return false;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        bool exist = false;
        for (int i = 0; i < users.size(); i++) {
            if (followerId == users[i].first) {
                exist = true;
                users[i].second.insert(followeeId);
                return;
            }
        }
        if (exist == false) {
            users.push_back({ followerId,{} });
            users[users.size() - 1].second.insert(followeeId);
        }
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        for (int i = 0; i < users.size(); i++) {
            if (followerId == users[i].first) {
                users[i].second.erase(followeeId);
                return;
            }
        }
    }
};

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */

优化部分

对函数 getNewsFeed(int userId) 进行了修改，并删除了函数 isFollowing(int id1, int id2)。

/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
vector<int> getNewsFeed(int userId) {
    vector<int> ans;
    //判断是否存在该id的用户
    bool exist = false;
    int index = -1;
    for (int i = 0; i < users.size(); i++) {
        if (userId == users[i].first) {
            index = i;
            break;
        }
    }
    //不存在直接返回空数组
    if (index == -1) {
        return ans;
    }
    int amount = tweets.size();
    int count = 0;
    for (int i = 0; count < 10 && i < tweets.size(); i++) {
        int cur = tweets[amount - i - 1].first;
        if (cur == userId || users[index].second.find(cur) != users[index].second.end()) {
            ans.push_back(tweets[amount - i - 1].second);
            count++;
        }
    }
    return ans;
}