355设计推特

小鱼儿 2023-02-26 13:23 11阅读 0赞

## 一、前言 ##

分类：Hash Table。

问题来源LeetCode 355 难度：中等。

问题链接：[https://leetcode-cn.com/problems/design-twitter/][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);

## 三、思路 ##

用 哈希表 + 链表 解决这道问题。

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 355_Twitter.h
    * @blogs   : 
    * @author  : niebingyu
    * @date    : 2020/07/15
    * @title   : 355. 设计推特
    * @purpose : 设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：
    * postTweet(userId, tweetId): 创建一条新的推文
    * getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
    * follow(followerId, followeeId): 关注一个用户
    * 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);
    *
    *
    * 来源：力扣（LeetCode）
    * 难度：简单
    * 链接：https://leetcode-cn.com/problems/design-twitter
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <unordered_set>
    #include <unordered_map>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_TWITTER namespace NAME_TWITTER {
    #define NAMESPACE_TWITTEREND }
    NAMESPACE_TWITTER
    
    class Twitter 
    {
        struct Node 
        {
            // 哈希表存储关注人的 Id
            unordered_set<int> followee;
            // 用链表存储 tweetId
            list<int> tweet;
        };
    
        // getNewsFeed 检索的推文的上限以及 tweetId 的时间戳
        int recentMax, time;
        // tweetId 对应发送的时间
        unordered_map<int, int> tweetTime;
        // 每个用户存储的信息
        unordered_map<int, Node> user;
    
    public:
        Twitter() 
        {
            time = 0;
            recentMax = 10;
            user.clear();
        }
        
        // 初始化
        void init(int userId) 
        {
            user[userId].followee.clear();
            user[userId].tweet.clear();
        }
    
        void postTweet(int userId, int tweetId) 
        {
            if (user.find(userId) == user.end()) 
                init(userId);
            
            // 达到限制，剔除链表末尾元素
            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> ans; ans.clear();
            for (list<int>::iterator it = user[userId].tweet.begin(); it != user[userId].tweet.end(); ++it) 
                ans.emplace_back(*it);
    
            for (int followeeId: user[userId].followee) 
            {
                if (followeeId == userId) continue; // 可能出现自己关注自己的情况
                vector<int> res; res.clear();
                list<int>::iterator it = user[followeeId].tweet.begin();
                int i = 0;
                // 线性归并
                while (i < (int)ans.size() && it != user[followeeId].tweet.end()) 
                {
                    if (tweetTime[(*it)] > tweetTime[ans[i]]) 
                    {
                        res.emplace_back(*it);
                        ++it;
                    } 
    				else 
                    {
                        res.emplace_back(ans[i]);
                        ++i;
                    }
    
                    // 已经找到这两个链表合起来后最近的 recentMax 条推文
                    if ((int)res.size() == recentMax) 
                        break;
                }
    
                for (; i < (int)ans.size() && (int)res.size() < recentMax; ++i) res.emplace_back(ans[i]);
                for (; it != user[followeeId].tweet.end() && (int)res.size() < recentMax; ++it) res.emplace_back(*it);
                ans.assign(res.begin(),res.end());
            }
            return ans;
        }
        
        void follow(int followerId, int followeeId) 
        {
            if (user.find(followerId) == user.end())
                init(followerId);
            
            if (user.find(followeeId) == user.end()) 
                init(followeeId);
            
            user[followerId].followee.insert(followeeId);
        }
        
        void unfollow(int followerId, int followeeId) 
        {
            user[followerId].followee.erase(followeeId);
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    // tweet: 发送推特， followee，关注
    void test(const char* testName, vector<pair<int, int>>& tweet, vector<pair<int, int>>& followee, int feedID, vector<int>& expect)
    {
        Twitter twitter;
        for (auto it: tweet)
            twitter.postTweet(it.first, it.second);
    
        for (auto it : followee)
            twitter.follow(it.first, it.second);
    
        vector<int> result = twitter.getNewsFeed(feedID);
    
        if (expect == result)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed." << endl;
    }
    
    // 发送推特
    vector<pair<int, int>> tweet1 =
    {
        {1,101},
        {1,102},
        {2,103},
        {3,104},
        {1,105},
        {3,106},
        {1,107},
        {2,108},
        {4,109},
        {3,110},
        {3,111},
        {3,112},
        {2,113},
        {4,114},
        {3,115},
        {5,116},
        {5,117},
        {5,118}
    };
    
    // 测试用例
    void Test1()
    {
        vector<pair<int, int>> followee =
        {
            {1,2},
            {2,3},
            {2,4},
            {2,5},
            {2,5}
        };
    
        int feedID = 1;
        vector<int> expect = {113,108,107,105,103,102,101};
        test("Test1()", tweet1, followee, feedID, expect);
    }
    
    void Test2()
    {
        vector<pair<int, int>> followee =
        {
            {1,2},
            {2,3},
            {2,4},
            {2,5},
            {1,5}
        };
    
        int feedID = 1;
        vector<int> expect = { 118,117,116,113,108,107,105,103,102,101 };
        test("Test2()", tweet1, followee, feedID, expect);
    }
    
    void Test3()
    {
        vector<pair<int, int>> followee =
        {
            {1,2},
            {1,3},
            {1,4},
            {1,5},
            {1,1}
        };
    
        int feedID = 1;
        vector<int> expect = { 118,117,116,115,114,113,112,111,110,109 };
        test("Test3()", tweet1, followee, feedID, expect);
    }
    
    NAMESPACE_TWITTEREND
    // 测试 用例 END
    //
    
    void Twitter_Test()
    {
        NAME_TWITTER::Test1();
        NAME_TWITTER::Test2();
        NAME_TWITTER::Test3();
    }

**执行结果：**

![20200715203311425.png][]

[https_leetcode-cn.com_problems_design-twitter]: https://leetcode-cn.com/problems/design-twitter/
[20200715203311425.png]: /images/20230209/04773278c8a64268b1ac457caa077e70.png