设计朋友圈时间线功能
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 355. Design Twitter | 355. 设计推特 | 🟠 |
———–
力扣第 355 「设计推特」不仅题目本身很有意思，而且把合并多个有序链表的算法和面向对象设计（OO design）结合起来了，很有实际意义，本文就带大家来看看这道题。
至于 Twitter 的什么功能跟算法有关系，等我们描述一下题目要求就知道了。
一、题目及应用场景简介
Twitter 和微博功能差不多，我们主要要实现这样几个 API：
class Twitter {
/** user 发表一条 tweet 动态 */
public void postTweet(int userId, int tweetId) {}
/** 返回该 user 关注的人（包括他自己）最近的动态 id，
最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列。*/
public List<Integer> getNewsFeed(int userId) {}
/** follower 关注 followee，如果 Id 不存在则新建 */
public void follow(int followerId, int followeeId) {}
/** follower 取关 followee，如果 Id 不存在则什么都不做 */
public void unfollow(int followerId, int followeeId) {}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Twitter {
public:
// user 发表一条 tweet 动态
void postTweet(int userId, int tweetId);
// 返回该 user 关注的人（包括他自己）最近的动态 id，
// 最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列
vector<int> getNewsFeed(int userId);
// follower 关注 followee，如果 Id 不存在则新建
void follow(int followerId, int followeeId);
// follower 取关 followee，如果 Id 不存在则什么都不做
void unfollow(int followerId, int followeeId);
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Twitter:
"""user 发表一条 tweet 动态"""
def postTweet(self, userId: int, tweetId: int) -> None:
pass
"""返回该 user 关注的人（包括他自己）最近的动态 id，
最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列。"""
def getNewsFeed(self, userId: int) -> List[int]:
pass
"""follower 关注 followee，如果 Id 不存在则新建"""
def follow(self, followerId: int, followeeId: int) -> None:
pass
"""follower 取关 followee，如果 Id 不存在则什么都不做"""
def unfollow(self, followerId: int, followeeId: int) -> None:
pass
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type Twitter struct {}
func (t *Twitter) postTweet(userId int, tweetId int) {}
// 返回该用户最近的动态id列表，最多10个，必须按照从新到旧的时间线顺序排列
func (t *Twitter) getNewsFeed(userId int) []int {}
// follower 关注 followee，如果 Id 不存在则新建
func (t *Twitter) follow(followerId int, followeeId int) {}
// follower 取关 followee，如果 Id 不存在则什么都不做
func (t *Twitter) unfollow(followerId int, followeeId int) {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var Twitter = function() {
/** user 发表一条 tweet 动态 */
this.postTweet = function(userId, tweetId) {}
/** 返回该 user 关注的人（包括他自己）最近的动态 id，
最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列。*/
this.getNewsFeed = function(userId) {}
/** follower 关注 followee，如果 Id 不存在则新建 */
this.follow = function(followerId, followeeId) {}
/** follower 取关 followee，如果 Id 不存在则什么都不做 */
this.unfollow = function(followerId, followeeId) {}
}
举个具体的例子，方便大家理解 API 的具体用法：
Twitter twitter = new Twitter();
twitter.postTweet(1, 5);
// 用户 1 发送了一条新推文 5
twitter.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]
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
Twitter twitter;
twitter.postTweet(1, 5);
// 用户 1 发送了一条新推文 5
twitter.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]
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
twitter = Twitter()
twitter.postTweet(1, 5)
# 用户 1 发送了一条新推文 5
twitter.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]
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// Create new Twitter instance
twitter := Constructor()
// Post tweet
twitter.PostTweet(1, 5)
// Expected output: 用户 1 发送了一条新推文 5
// Get news feed
newsFeed := twitter.GetNewsFeed(1)
fmt.Println(newsFeed)
// Expected output: [5]，因为自己是关注自己的
// Follow user
twitter.Follow(1, 2)
// Expected output: 用户 1 关注了用户 2
// Post tweet
twitter.PostTweet(2, 6)
// Expected output: 用户2发送了一个新推文 (id = 6)
// Get news feed
newsFeed = twitter.GetNewsFeed(1)
fmt.Println(newsFeed)
// Expected output: [6, 5]
// 解释：用户 1 关注了自己和用户 2，所以返回他们的最近推文
// 而且 6 必须在 5 之前，因为 6 是最近发送的
// Unfollow user
twitter.Unfollow(1, 2)
// Expected output: 用户 1 取消关注了用户 2
// Get news feed
newsFeed = twitter.GetNewsFeed(1)
fmt.Println(newsFeed)
// Expected output: [5]
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var twitter = new Twitter();
twitter.postTweet(1, 5);
// 用户 1 发送了一条新推文 5
twitter.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 类，储存推文信息，并且要作为链表的节点。所以我们先搭建一下整体的框架：
class Twitter {
private static int timestamp = 0;
private static class Tweet {}
private static class User {}
/* 还有那几个 API 方法 */
public void postTweet(int userId, int tweetId) {}
public List<Integer> getNewsFeed(int userId) {}
public void follow(int followerId, int followeeId) {}
public void unfollow(int followerId, int followeeId) {}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
#include <bits/stdc++.h>
using namespace std;
class Twitter {
private:
/*
* timestamp 记录的是推文发布时间
* Tweet 是一个推文，保存了发布者的 id 和该推文的发布时间
* User 是一个用户，保存了他关注的人列表和推文列表
*/
static int timestamp;
struct Tweet {};
struct User {};
public:
/*
* 用户发布一条 tweet 动态
*/
void postTweet(int userId, int tweetId) {};
/*
* 获取一个用户关注的人（包括自己）的最近的动态推文
*/
vector<int> getNewsFeed(int userId) {};
/*
* followerId 关注 followeeId，成功返回 1，如果 Id 不在 User 集合内返回 0。
*/
void follow(int followerId, int followeeId) {};
/*
* followerId 取消关注 followeeId，如果 Id 不在 User 集合内则方法无效。
*/
void unfollow(int followerId, int followeeId) {};
};
int Twitter::timestamp = 0;
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Twitter:
timestamp = 0 # 记录时间戳
class Tweet: # 推文类
pass
class User: # 用户类
pass
def postTweet(self, userId: int, tweetId: int) -> None: # 发布一条推文
pass
def getNewsFeed(self, userId: int) -> List[int]: # 获取用户的所有关注者（包括自己）最近的推特，最多10条
pass
def follow(self, followerId: int, followeeId: int) -> None: # 关注一个用户
pass
def unfollow(self, followerId: int, followeeId: int) -> None: # 取消关注一个用户
pass
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var timestamp = 0
type Tweet struct{}
type User struct{}
type Twitter struct {}
// 还有那几个 API 方法
func (t *Twitter) postTweet(userId int, tweetId int) {}
func (t *Twitter) getNewsFeed(userId int) []int {return nil}
func (t *Twitter) follow(followerId int, followeeId int) {}
func (t *Twitter) unfollow(followerId int, followeeId int) {}
func main() {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var Twitter = function() {
var timestamp = 0;
var Tweet = function() {};
var User = function() {};
/* 还有那几个 API 方法 */
this.postTweet = function(userId, tweetId) {};
this.getNewsFeed = function(userId) {};
this.follow = function(followerId, followeeId) {};
this.unfollow = function(followerId, followeeId) {};
};
之所以要把 Tweet 和 User 类放到 Twitter 类里面，是因为 Tweet 类必须要用到一个全局时间戳 timestamp，而 User 类又需要用到 Tweet 类记录用户发送的推文，所以它们都作为内部类。不过为了清晰和简洁，下文会把每个内部类和 API 方法单独拿出来实现。
1、Tweet 类的实现
根据前面的分析，Tweet 类很容易实现：每个 Tweet 实例需要记录自己的 tweetId 和发表时间 time，而且作为链表节点，要有一个指向下一个节点的 next 指针。
class Tweet {
private int id;
private int time;
private Tweet next;
// 需要传入推文内容（id）和发文时间
public Tweet(int id, int time) {
this.id = id;
this.time = time;
this.next = null;
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Tweet {
private:
int id;
int time;
Tweet* next;
public:
// 构造函数，需要传入推文内容（id）和发文时间
Tweet(int id, int time) {
this->id = id;
this->time = time;
this->next = NULL;
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Tweet:
def __init__(self, id: int, time: int):
# 需要传入推文内容（id）和发文时间
self.id = id
self.time = time
self.next = None
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type Tweet struct {
id int
time int
next *Tweet
}
// 需要传入推文内容（id）和发文时间
func NewTweet(id int, time int) *Tweet {
return &Tweet{id: id, time: time, next: nil}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 需要传入推文内容（id）和发文时间
function Tweet(id, time) {
var id = id;
var time = time;
var next = null;
}
2、User 类的实现
我们根据实际场景想一想，一个用户需要存储的信息有 userId，关注列表，以及该用户发过的推文列表。其中关注列表应该用集合（Hash Set）这种数据结构来存，因为不能重复，而且需要快速查找；推文列表应该由链表这种数据结构储存，以便于进行有序合并的操作。画个图理解一下：
除此之外，根据面向对象的设计原则，「关注」「取关」和「发文」应该是 User 的行为，况且关注列表和推文列表也存储在 User 类中，所以我们也应该给 User 添加 follow，unfollow 和 post 这几个方法：
// static int timestamp = 0
class User {
private int id;
public Set<Integer> followed;
// 用户发表的推文链表头结点
public Tweet head;
public User(int userId) {
followed = new HashSet<>();
this.id = userId;
this.head = null;
// 关注一下自己
follow(id);
}
public void follow(int userId) {
followed.add(userId);
}
public void unfollow(int userId) {
// 不可以取关自己
if (userId != this.id)
followed.remove(userId);
}
public void post(int tweetId) {
Tweet twt = new Tweet(tweetId, timestamp);
timestamp++;
// 将新建的推文插入链表头
// 越靠前的推文 time 值越大
twt.next = head;
head = twt;
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// static int timestamp = 0
class User {
private:
int id;
set<int> followed;
// 用户发表的推文链表头结点
Tweet* head;
public:
User(int userId) {
followed = set<int>();
this->id = userId;
this->head = NULL;
// 关注一下自己
follow(id);
}
void follow(int userId) {
followed.insert(userId);
}
void unfollow(int userId) {
// 不可以取关自己
if (userId != this->id)
followed.erase(userId);
}
void post(int tweetId) {
Tweet* twt = new Tweet(tweetId, timestamp);
timestamp++;
// 将新建的推文插入链表头
// 越靠前的推文 time 值越大
twt->next = head;
head = twt;
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class User:
# 用户类，包含用户关注的人、推文的链表头结点、用户 ID
def __init__(self, userId: int):
self.id = userId
self.followed = set() # 用户关注的人
self.head = None # 推文的链表头结点
self.follow(self.id) # 关注自己
# 用户关注一个人
def follow(self, userId: int):
self.followed.add(userId)
# 用户取消关注一个人
def unfollow(self, userId: int):
# 不可以取关自己
if userId != self.id:
self.followed.remove(userId)
# 用户发表一条推文
def post(self, tweetId: int):
twt = Tweet(tweetId, timestamp)
global timestamp # 全局时间戳，保证推文各不相同
timestamp += 1 # 时间戳自增
# 将新建的推文插入链表头
# 越靠前的推文 time 值越大
twt.next = self.head
self.head = twt
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// static int timestamp = 0
type User struct {
id int
followed map[int]bool // 用户关注其他用户的集合
head *Tweet // 用户发布的推文链表
}
func NewUser(userId int) *User {
user := User{
id: userId,
followed: make(map[int]bool),
}
user.follow(userId) // 关注自己
return &user
}
func (u *User) follow(userId int) {
u.followed[userId] = true
}
func (u *User) unfollow(userId int) {
// 不可以取关自己
if userId != u.id {
delete(u.followed, userId)
}
}
func (u *User) post(tweetId int) {
tweet := NewTweet(tweetId, timestamp)
timestamp++
// 插入链表头
tweet.next = u.head
u.head = tweet
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var timestamp = 0;
class User {
constructor(userId) {
this.id = userId;
this.followed = new Set();
this.head = null;
// 关注一下自己
this.follow(this.id);
}
follow(userId) {
this.followed.add(userId);
}
unfollow(userId) {
// 不可以取消关注自己
if (userId !== this.id) {
this.followed.delete(userId);
}
}
post(tweetId) {
var twt = new Tweet(tweetId, timestamp);
timestamp++;
// 将新建的推文插入链表头
// 越靠前的推文 time 值越大
twt.next = this.head;
this.head = twt;
}
}
3、几个 API 方法的实现
class Twitter {
private static int timestamp = 0;
private static class Tweet {...}
private static class User {...}
// 我们需要一个映射将 userId 和 User 对象对应起来
private HashMap<Integer, User> userMap = new HashMap<>();
/** user 发表一条 tweet 动态 */
public void postTweet(int userId, int tweetId) {
// 若 userId 不存在，则新建
if (!userMap.containsKey(userId))
userMap.put(userId, new User(userId));
User u = userMap.get(userId);
u.post(tweetId);
}
/** follower 关注 followee */
public void follow(int followerId, int followeeId) {
// 若 follower 不存在，则新建
if(!userMap.containsKey(followerId)){
User u = new User(followerId);
userMap.put(followerId, u);
}
// 若 followee 不存在，则新建
if(!userMap.containsKey(followeeId)){
User u = new User(followeeId);
userMap.put(followeeId, u);
}
userMap.get(followerId).follow(followeeId);
}
/** follower 取关 followee，如果 Id 不存在则什么都不做 */
public void unfollow(int followerId, int followeeId) {
if (userMap.containsKey(followerId)) {
User flwer = userMap.get(followerId);
flwer.unfollow(followeeId);
}
}
/** 返回该 user 关注的人（包括他自己）最近的动态 id，
最多 10 条，而且这些动态必须按从新到旧的时间线顺序排列。*/
public List<Integer> getNewsFeed(int userId) {
// 需要理解算法，见下文
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
#include <unordered_map>
#include <vector>
using namespace std;
class Twitter {
private:
static int timestamp;
struct Tweet {...};
struct User {...};
unordered_map<int, User> userMap;
public:
void postTweet(int userId, int tweetId) {
if (userMap.find(userId) == userMap.end()) {
userMap.insert({userId, User(userId)});
}
User& u = userMap[userId];
u.post(tweetId);
}
void follow(int followerId, int followeeId) {
if (userMap.find(followerId) == userMap.end()) {
User u(followerId);
userMap.insert({followerId, u});
}
if (userMap.find(followeeId) == userMap.end()) {
User u(followeeId);
userMap.insert({followeeId, u});
}
userMap[followerId].follow(followeeId);
}
void unfollow(int followerId, int followeeId) {
if (userMap.find(followerId) != userMap.end()) {
User& flwer = userMap[followerId];
flwer.unfollow(followeeId);
}
}
vector<int> getNewsFeed(int userId) {
// 需要理解算法，见下文
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Twitter:
timestamp = 0
class Tweet:
"""Tweet类用于定位tweet"""
pass
class User:
"""User类用于记录用户信息"""
pass
def __init__(self):
"""初始化，创建一个字典，用于userId和user对象的映射"""
self.userMap = {}
def postTweet(self, userId: int, tweetId: int) -> None:
"""用户userId发表一条tweet"""
if userId not in self.userMap:
self.userMap[userId] = User(userId)
u = self.userMap[userId]
u.post(tweetId)
def follow(self, followerId: int, followeeId: int) -> None:
"""用户followerId关注用户followeeId"""
if followerId not in self.userMap:
u = User(followerId)
self.userMap[followerId] = u
if followeeId not in self.userMap:
u = User(followeeId)
self.userMap[followeeId] = u
self.userMap[followerId].follow(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
"""用户followerId取消关注用户followeeId"""
if followerId in self.userMap:
flwer = self.userMap[followerId]
flwer.unfollow(followeeId)
def getNewsFeed(self, userId: int) -> List[int]:
"""返回该用户关注的人最近的动态，最多10条"""
pass
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type Twitter struct {
userMap map[int]*User
}
type User struct {
id int
followees map[int]bool
tweets []*Tweet
}
type Tweet struct {
id int
time int
}
// 推特数目，用于时间排序
var tweetCount int
func Constructor() Twitter {
return Twitter{userMap: make(map[int]*User)}
}
func (t *Twitter) PostTweet(userId int, tweetId int) {
if _, ok := t.userMap[userId]; !ok {
t.userMap[userId] = &User{
id: userId,
followees: make(map[int]bool),
}
}
t.userMap[userId].tweets = append(t.userMap[userId].tweets, &Tweet{
id: tweetId,
time: tweetCount,
})
tweetCount++
}
func (t *Twitter) Follow(followerId int, followeeId int) {
if _, ok := t.userMap[followerId]; !ok {
t.userMap[followerId] = &User{
id: followerId,
followees: make(map[int]bool),
}
}
if _, ok := t.userMap[followeeId]; !ok {
t.userMap[followeeId] = &User{
id: followeeId,
followees: make(map[int]bool),
}
}
t.userMap[followerId].followees[followeeId] = true
}
func (t *Twitter) Unfollow(followerId int, followeeId int) {
if _, ok := t.userMap[followerId]; ok {
delete(t.userMap[followerId].followees, followeeId)
}
}
func (t *Twitter) GetNewsFeed(userId int) []int {
var result []int
if user, ok := t.userMap[userId]; ok {
// 所有关注者的所有推文
tweets := make([]*Tweet, 0)
for followeeId := range user.followees {
if followee, ok := t.userMap[followeeId]; ok {
tweets = append(tweets, followee.tweets...)
}
}
tweets = append(tweets, user.tweets...)
// 按时间顺序逆序排列
sort.Slice(tweets, func(i, j int) bool {
return tweets[i].time > tweets[j].time
})
for _, tweet := range tweets {
result = append(result, tweet.id)
if len(result) == 10 {
break
}
}
}
return result
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var Twitter = function() {
var timestamp = 0;
var Tweet = function(tweetId, timestamp) {...};
var User = function(userId) {...};
var userMap = {};
this.postTweet = function(userId, tweetId) {
// 若 userId 不存在，则新建
if (!userMap[userId]) {
userMap[userId] = new User(userId);
}
var u = userMap[userId];
u.post(tweetId);
};
this.follow = function(followerId, followeeId) {
// 若 follower 不存在，则新建
if(!userMap[followerId]) {
var u = new User(followerId);
userMap[followerId] = u;
}
// 若 followee 不存在，则新建
if(!userMap[followeeId]) {
var u = new User(followeeId);
userMap[followeeId] = u;
}
userMap[followerId].follow(followeeId);
};
this.unfollow = function(followerId, followeeId) {
if (userMap[followerId]) {
var flwer = userMap[followerId];
flwer.unfollow(followeeId);
}
};
this.getNewsFeed = function(userId) {
// 需要理解算法，见下文
};
};
三、算法设计
实现合并 k 个有序链表的算法需要用到优先级队列（Priority Queue），这种数据结构是「二叉堆」最重要的应用，你可以理解为它可以对插入的元素自动排序。乱序的元素插入其中就被放到了正确的位置，可以按照从小到大（或从大到小）有序地取出元素。
PriorityQueue pq
# 乱序插入
for i in {2,4,1,9,6}:
pq.add(i)
while pq not empty:
# 每次取出第一个（最小）元素
print(pq.pop())
# 输出有序：1,2,4,6,9
借助这种牛逼的数据结构支持，我们就很容易实现这个核心功能了。注意我们把优先级队列设为按 time 属性从大到小降序排列，因为 time 越大意味着时间越近，应该排在前面：
class Twitter {
// 为了节约篇幅，省略上文给出的代码部分...
public List<Integer> getNewsFeed(int userId) {
List<Integer> res = new ArrayList<>();
if (!userMap.containsKey(userId)) return res;
// 关注列表的用户 Id
Set<Integer> users = userMap.get(userId).followed;
// 自动通过 time 属性从大到小排序，容量为 users 的大小
PriorityQueue<Tweet> pq =
new PriorityQueue<>(users.size(), (a, b)->(b.time - a.time));
// 先将所有链表头节点插入优先级队列
for (int id : 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);
}
return res;
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Twitter {
// 为了节约篇幅，省略上文给出的代码部分...
public:
vector<int> getNewsFeed(int userId) {
vector<int> res;
if (!userMap.count(userId)) return res;
// 关注列表的用户 Id
set<int>& users = userMap[userId].followed;
// 自动通过 time 属性从大到小排序，容量为 users 的大小
priority_queue<Tweet*, vector<Tweet*>, TweetCompare> pq;
// 先将所有链表头节点插入优先级队列
for (auto id : users) {
Tweet* twt = userMap[id].head;
if (twt == nullptr) continue;
pq.push(twt);
}
while (!pq.empty()) {
// 最多返回 10 条就够了
if (res.size() == 10) break;
// 弹出 time 值最大的（最近发表的）
Tweet* twt = pq.top();
pq.pop();
res.push_back(twt->id);
// 将下一篇 Tweet 插入进行排序
if (twt->next != nullptr)
pq.push(twt->next);
}
return res;
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
import heapq
class Twitter:
def getNewsFeed(self, userId: int) -> List[int]:
res = []
if userId not in self.userMap: # 如果不存在 userId 则返回空结果列表
return res
users = self.userMap[userId].followed
# 用最大堆存储所有关注列表的 Tweet，时间复杂度 logN
pq = []
for id in users:
twt = self.userMap[id].head
if twt:
# 将time取相反数作为堆的排序值，使其成为最大堆
heapq.heappush(pq, (-twt.time, twt))
# 检查队列中是否有Tweet的时间最晚或已经取到10个Tweet的时候退出
while pq and len(res) < 10:
_, twt = heapq.heappop(pq)
res.append(twt.id)
if twt.next:
# 将一个用户发布的下一个Tweet放入最大堆中对其排序
heapq.heappush(pq, (-twt.next.time, twt.next))
return res
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type Twitter struct {
// 为了节约篇幅，省略上文给出的代码部分...
}
func (this *Twitter) GetNewsFeed(userId int) []int {
res := []int{}
if _, ok := this.userMap[userId]; !ok {
return res
}
// 关注列表的用户 ID
users := this.userMap[userId].followed
// 自动通过 time 属性从大到小排序，容量为 users 的大小
pq := priorityQueue{}
for _, id := range users {
if twt := this.userMap[id].head; twt != nil {
pq.push(*twt)
}
}
for len(pq) > 0 {
// 最多返回 10 条就够了
if len(res) == 10 {
break
}
// 弹出 time 值最大的（最近发表的）
twt := pq.pop()
res = append(res, twt.id)
// 将下一篇 Tweet 插入进行排序
if twt.next != nil {
pq.push(*twt.next)
}
}
return res
}
type priorityQueue []Tweet
func (pq priorityQueue) Len() int {
return len(pq)
}
func (pq priorityQueue) Less(i, j int) bool {
return pq[i].time > pq[j].time
}
func (pq priorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *priorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(Tweet))
}
func (pq *priorityQueue) Pop() interface{} {
n := len(*pq)
x := (*pq)[n-1]
*pq = (*pq)[:n-1]
return x
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var Twitter = function() {
// 为了节约篇幅，省略上文给出的代码部分...
this.getNewsFeed = function(userId) {
var res = [];
if (!userMap.hasOwnProperty(userId)) return res;
// 关注列表的用户 Id
var users = userMap[userId].followed;
// 自动通过 time 属性从大到小排序，容量为 users 的大小
var pq = new PriorityQueue(users.size(), function(a, b) { return b.time - a.time; });
// 先将所有链表头节点插入优先级队列
for (var id in users) {
var twt = userMap[id].head;
if (!twt) continue;
pq.add(twt);
}
while (!pq.isEmpty()) {
// 最多返回 10 条就够了
if (res.length == 10) break;
// 弹出 time 值最大的（最近发表的）
var twt = pq.poll();
res.push(twt.id);
// 将下一篇 Tweet 插入进行排序
if (twt.next)
pq.add(twt.next);
}
return res;
};
};
这个过程是这样的，下面是我制作的一个 GIF 图描述合并链表的过程。假设有三个 Tweet 链表按 time 属性降序排列，我们把他们降序合并添加到 res 中。注意图中链表节点中的数字是 time 属性，不是 id 属性：
至此，这道一个极其简化的 Twitter 时间线功能就设计完毕了。
四、最后总结
本文运用简单的面向对象技巧和合并 k 个有序链表的算法设计了一套简化的时间线功能，这个功能其实广泛地运用在许多社交应用中。
我们先合理地设计出 User 和 Tweet 两个类，然后基于这个设计之上运用算法解决了最重要的一个功能。可见实际应用中的算法并不是孤立存在的，需要和其他知识混合运用，才能发挥实际价值。
当然，实际应用中的社交 App 数据量是巨大的，考虑到数据库的读写性能，我们的设计可能承受不住流量压力，还是有些太简化了。而且实际的应用都是一个极其庞大的工程，比如下图，是 Twitter 这样的社交网站大致的系统结构：
我们解决的问题应该只能算 Timeline Service 模块的一小部分，功能越多，系统的复杂性可能是指数级增长的。所以说合理的顶层设计十分重要，其作用是远超某一个算法的。Github 上有一个优秀的开源项目，专门收集了很多大型系统设计的案例和解析，而且有中文版本，上面这个图也出自该项目。对系统设计感兴趣的读者可以点击 这里 查看。
本文就到这里，更多数据结构设计相关的题目参见 数据结构设计经典习题。
引用本文的文章
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释