念完责任编辑，你能去力扣夺下如下表所示试题：

355.结构设计twitter

-----------

「design Twitter」是 LeetCode 上第 355 道试题，不但试题这类很有趣，所以把分拆数个科学规范二叉树的演算法和程序语言结构设计（OO design）紧密结合出来了，很有实用价值，责任编辑就带我们来看一看这道题。

再者 Twitter 的甚么机能跟演算法有亲密关系，等他们叙述呵呵试题明确要求就晓得了。

一、试题及应用领域情景概要

Twitter 和博客机能相差无几，他们主要就要同时实现这种两个 API：

classTwitter{/** user 刊登两条 tweet 静态 */publicvoidpostTweet(intuserId,inttweetId){}/** 返回该 user 关注的人（包括他自己）最近的静态 id，
    最多 10 条，所以这些静态必须按从新到旧的时间线顺序排列。*/publicListgetNewsFeed(intuserId){}/** follower 关注 followee，如果 Id 不存在则新建 */publicvoidfollow(intfollowerId,intfolloweeId){}/** follower 取关 followee，如果 Id 不存在则甚么都不做 */publicvoidunfollow(intfollowerId,intfolloweeId){}
}

举个具体的例子，方便我们理解 API 的具体用法：

Twittertwitter=newTwitter();twitter.postTweet(1,5);//用户1发送了两条新推文5twitter.getNewsFeed(1);//return[5]，因为自己是关注自己的​twitter.follow(1,2);//用户1关注了用户2​twitter.postTweet(2,6);//用户2发送了一个新推文(id=6)​twitter.getNewsFeed(1);//return[6,5]//解释：用户1关注了自己和用户2，所以返回他们的最近推文//所以6必须在5之前，因为6是最近发送的​twitter.unfollow(1,2);//用户1取消关注了用户2​twitter.getNewsFeed(1);//return[5]

这个情景在他们的现实生活中非常常见。拿朋友圈举例，比如我刚加到女神的，然后我去刷新呵呵我的朋友圈静态，那么女神的静态就会出现在我的静态列表，所以会和其他静态按时间排好序。只不过 Twitter 是单向关注，好友相当于双向关注。除非，被屏蔽...

这两个 API 中大部分都很好同时实现，最核心的机能难点应该是getNewsFeed，因为返回的结果必须在时间上科学规范，但问题是用户的关注是静态变化的，怎么办？

这里就涉及到演算法了：如果他们把每个用户各自的推文存储在二叉树里，每个二叉树节点存储文章 id 和一个时间戳 time（记录发帖时间以便比较），所以这个二叉树是按 time 科学规范的，那么如果某个用户关注了 k 个用户，他们就能用分拆 k 个科学规范二叉树的演算法分拆出科学规范的推文列表，正确地getNewsFeed了！

具体的演算法等会讲解。不过，就算他们掌握了演算法，应该如何编程表示用户 user 和推文静态 tweet 才能把演算法流畅地用出来呢？这就涉及简单的程序语言结构设计了，下面他们来由浅入深，一步一步进行结构设计。

二、程序语言结构设计

根据刚才的分析，他们需要一个 User 类，储存 user 信息，还需要一个 Tweet 类，储存推文信息，并且要作为二叉树的节点。所以他们先搭建呵呵整体的框架：

classTwitter{privatestaticinttimestamp =0;privatestaticclassTweet{}privatestaticclassUser{}
​/* 还有那两个 API 方法 */publicvoidpostTweet(intuserId,inttweetId){}publicListgetNewsFeed(intuserId){}publicvoidfollow(intfollowerId,intfolloweeId){}publicvoidunfollow(intfollowerId,intfolloweeId){}
}

之所以要把 Tweet 和 User 类放到 Twitter 类里面，是因为 Tweet 类必须要用到一个全局时间戳 timestamp，而 User 类又需要用到 Tweet 类记录用户发送的推文，所以它们都作为内部类。不过为了清晰和简洁，下文会把每个内部类和 API 方法单独拿出来同时实现。

1、Tweet 类的同时实现

根据前面的分析，Tweet 类很容易同时实现：每个 Tweet 实例需要记录自己的 tweetId 和刊登时间 time，所以作为二叉树节点，要有一个指向下一个节点的 next 指针。

classTweet{privateintid;privateinttime;privateTweet next;
​// 需要传入推文内容（id）和发文时间publicTweet(intid,inttime){this.id = id;this.time = time;this.next =null;
    }
}

2、User 类的同时实现

他们根据实际情景想一想，一个用户需要存储的信息有 userId，关注列表，以及该用户发过的推文列表。其中关注列表应该用集合（Hash Set）这种数据结构来存，因为不能重复，所以需要快速查找；推文列表应该由二叉树这种数据结构储存，以便于进行科学规范分拆的操作。画个图理解呵呵：

除此之外，根据程序语言的结构设计原则，「关注」「取关」和「发文」应该是 User 的行为，况且关注列表和推文列表也存储在 User 类中，所以他们也应该给 User 添加 follow，unfollow 和 post 这两个方法：

// static int timestamp = 0classUser{privateintid;publicSet followed;// 用户刊登的推文二叉树头结点publicTweet head;
​publicUser(intuserId){
        followed =newHashSet<>();this.id = userId;this.head =null;// 关注呵呵自己follow(id);
    }
​publicvoidfollow(intuserId){
        followed.add(userId);
    }
​publicvoidunfollow(intuserId){// 不能取关自己if(userId !=this.id)
            followed.remove(userId);
    }
​publicvoidpost(inttweetId){
        Tweet twt =newTweet(tweetId, timestamp);
        timestamp++;// 将新建的推文插入二叉树头// 越靠前的推文 time 值越大twt.next = head;
        head = twt;
    }
}

3、两个 API 方法的同时实现

classTwitter{privatestaticinttimestamp =0;privatestaticclassTweet{...}privatestaticclassUser{...}
​// 他们需要一个映射将 userId 和 User 对象对应出来privateHashMap userMap =newHashMap<>();
​/** user 刊登两条 tweet 静态 */publicvoidpostTweet(intuserId,inttweetId){// 若 userId 不存在，则新建if(!userMap.containsKey(userId))
            userMap.put(userId,newUser(userId));
        User u = userMap.get(userId);
        u.post(tweetId);
    }/** follower 关注 followee */publicvoidfollow(intfollowerId,intfolloweeId){// 若 follower 不存在，则新建if(!userMap.containsKey(followerId)){
            User u =newUser(followerId);
            userMap.put(followerId, u);
        }// 若 followee 不存在，则新建if(!userMap.containsKey(followeeId)){
            User u =newUser(followeeId);
            userMap.put(followeeId, u);
        }
        userMap.get(followerId).follow(followeeId);
    }/** follower 取关 followee，如果 Id 不存在则甚么都不做 */publicvoidunfollow(intfollowerId,intfolloweeId){if(userMap.containsKey(followerId)) {
            User flwer = userMap.get(followerId);
            flwer.unfollow(followeeId);
        }
    }
​/** 返回该 user 关注的人（包括他自己）最近的静态 id，
    最多 10 条，所以这些静态必须按从新到旧的时间线顺序排列。*/publicListgetNewsFeed(intuserId){// 需要理解演算法，见下文}
}

三、演算法结构设计

同时实现分拆 k 个科学规范二叉树的演算法需要用到优先级队列（Priority Queue），这种数据结构是「二叉堆」最重要的应用领域，你能理解为它能对插入的元素自动排序。乱序的元素插入其中就被放到了正确的位置，能按照从小到大（或从大到小）科学规范地取出元素。

PriorityQueue pq乱序插入fori in {2,4,1,9,6}:
    pq.add(i)whilepq notempty:每次取出第一个（最小）元素print(pq.pop())
​输出科学规范：1,2,4,6,9

借助这种牛逼的数据结构支持，他们就很容易同时实现这个核心机能了。注意他们把优先级队列设为按 time 属性从大到小降序排列，因为 time 越大意味着时间越近，应该排在前面：

publicListgetNewsFeed(intuserId){
    List res =newArrayList<>();if(!userMap.containsKey(userId))returnres;// 关注列表的用户 IdSet users = userMap.get(userId).followed;// 自动通过 time 属性从大到小排序，容量为 users 的大小PriorityQueue pq =newPriorityQueue<>(users.size(), (a, b)->(b.time - a.time));
​// 先将所有二叉树头节点插入优先级队列for(intid : users) {
        Tweet twt = userMap.get(id).head;if(twt ==null)continue;
        pq.add(twt);
    }
​while(!pq.isEmpty()) {// 最多返回 10 条就够了if(res.size() ==10)break;// 弹出 time 值最大的（最近刊登的）Tweet twt = pq.poll();
        res.add(twt.id);// 将下一篇 Tweet 插入进行排序if(twt.next !=null) 
            pq.add(twt.next);
    }returnres;
}

这个过程是这种的，下面是我制作的一个 GIF 图叙述分拆二叉树的过程。假设有三个 Tweet 二叉树按 time 属性降序排列，他们把他们降序分拆添加到 res 中。注意图中二叉树节点中的数字是 time 属性，不是 id 属性：

至此，这道一个极其简化的 Twitter 时间线机能就结构设计完毕了。

四、最后总结

责任编辑运用简单的程序语言技巧和分拆 k 个科学规范二叉树的演算法结构设计了一套简化的时间线机能，这个机能其实广泛地运用在许多社交应用领域中。

他们先合理地结构设计出 User 和 Tweet 两个类，然后基于这个结构设计之上运用演算法解决了最重要的一个机能。可见实际应用领域中的演算法并不是孤立存在的，需要和其他知识混合运用，才能发挥实际价值。

当然，实际应用领域中的社交 App 数据量是巨大的，考虑到数据库的读写性能，他们的结构设计可能承受不住流量压力，还是有些太简化了。所以实际的应用领域都是一个极其庞大的工程，比如下表所示图，是 Twitter 这种的社交网站大致的系统结构：

他们解决的问题应该只能算 Timeline Service 模块的一小部分，机能越多，系统的复杂性可能是指数级增长的。所以说合理的顶层结构设计十分重要，其作用是远超某一个演算法的。

最后，Github 上有一个优秀的开源项目，专门收集了很多大型系统结构设计的案例和解析，所以有中文版本，上面这个图也出自该项目。对系统结构设计感兴趣的读者能点击 这里 查看。

PS：责任编辑前两张图片和 GIF 是我第一次尝试用平板的绘图软件制作的，花了很多时间，尤其是 GIF 图，需要一帧一帧制作。如果责任编辑内容对你有帮助，点个赞分个享，鼓励呵呵我呗！

→CL自助下单平台←