力扣355.设计推特

力扣355.设计推特

• 设计Node类有哈希集合存关注人的Id，有链表存推文的顺序

  • 一个哈希表存推文的时间

•   class Twitter {
        struct Node{
            unordered_set<int> followee;
            list<int> tweet;
        };
        int recentMax,time;
        unordered_map<int,int> tweettime;
        unordered_map<int,Node> user;
    public:
        Twitter() {
            //当前时间
            time = 0;
            //最大推文数
            recentMax = 10;
            user.clear();
        }
    
        void postTweet(int userId, int tweetId) 
        {  
            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> res;
            for(auto it = user[userId].tweet.begin();it != user[userId].tweet.end();it++)
                res.emplace_back(*it);
            //遍历每个关注人 合并链表
            for(int followeeId : user[userId].followee)
            {
                if(followeeId == userId) continue;
                vector<int> ans;
                auto it = user[followeeId].tweet.begin();
                int i = 0;
                while(i<(int)res.size() && it != user[followeeId].tweet.end())
                {
                    if(tweettime[(*it)] > tweettime[res[i]])
                    {
                        ans.emplace_back(*it);
                        it++;
                    }
                    else
                    {
                        ans.emplace_back(res[i]);
                        i++;
                    }
                    if((int)ans.size() == recentMax) break;
                }
                //如果数量不够 并且res还有剩余
                for(;i<(int)res.size() && (int)ans.size() < recentMax;i++)
                    ans.emplace_back(res[i]);
                //如果数量不够 并且关注人还有剩余
                for(;it != user[followeeId].tweet.end() && (int)ans.size() < recentMax;it++)
                    ans.emplace_back(*it);
                //ans赋给res
                res.assign(ans.begin(),ans.end());
            }
            return res;
        }
        
        void follow(int followerId, int followeeId) {
            user[followerId].followee.insert(followeeId);
        }
        
        void unfollow(int followerId, int followeeId) {
            user[followerId].followee.erase(followeeId);
        }
    };
  

原文地址：https://blog.csdn.net/Pisasama/article/details/140602375

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！