Info
新版网站会员 即将涨价;已支持老用户续费~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
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 条,而且这些动态必须按从新到旧的时间线顺序排列
std::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 {}
// user 发表一条 tweet 动态
func (t Twitter) postTweet(userId int, tweetId int) {}
// 返回该 user 关注的人(包括他自己)最近的动态 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 代码对比查看。
twitter := Constructor();
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]
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var Twitter = function() {
this.twitter = new Twitter();
};
Twitter.prototype.postTweet = function(userId, tweetId) {
// 用户userId发表了一条新推文tweetId
};
Twitter.prototype.getNewsFeed = function(userId) {
// 获取用户userId的动态,包括自己和关注的人的最近推文,按照时间倒序排序
};
Twitter.prototype.follow = function(followerId, followeeId) {
// 用户followerId关注了用户followeeId
};
Twitter.prototype.unfollow = function(followerId, followeeId) {
// 用户followerId取消关注了用户followeeId
};
var twitter = new Twitter();
twitter.postTweet(1, 5);
twitter.getNewsFeed(1);
twitter.follow(1, 2);
twitter.postTweet(2, 6);
twitter.getNewsFeed(1);
twitter.unfollow(1, 2);
twitter.getNewsFeed(1);
这个场景在我们的现实生活中非常常见。拿朋友圈举例,比如我刚加到女神的微信,然后我去刷新一下我的朋友圈动态,那么女神的动态就会出现在我的动态列表,而且会和其他动态按时间排好序。只不过 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 代码对比查看。
class Twitter {
private:
static int timestamp; // 时间戳
class Tweet {}; // 推文类
class User {}; // 用户类
public:
// API 方法
void postTweet(int userId, int tweetId) {} // 发布推文
std::vector<int> getNewsFeed(int userId) {} // 获取用户的新闻feed
void follow(int followerId, int followeeId) {} // 关注用户
void unfollow(int followerId, int followeeId) {} // 取消关注用户
};
// Initialize static member variable
int Twitter::timestamp = 0;
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Twitter:
timestamp = 0
class Tweet:
pass
class User:
pass
# 还有那几个 API 方法
def postTweet(self, userId: int, tweetId: int):
pass
def getNewsFeed(self, userId: int) -> list[int]:
pass
def follow(self, followerId: int, followeeId: int):
pass
def unfollow(self, followerId: int, followeeId: int):
pass
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
type Tweet struct {}
type User struct {}
var timestamp int = 0
type Twitter struct {}
// 还有那几个 API 方法
func (t *Twitter) postTweet(userId int, tweetId int) {}
func (t *Twitter) getNewsFeed(userId int) []int {}
func (t *Twitter) follow(followerId int, followeeId int) {}
func (t *Twitter) unfollow(followerId int, followeeId int) {}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var timestamp = 0; // private static int timestamp = 0;
var Tweet = function() {}; // private static class Tweet {}
var User = function() {}; // private static class User {}
// 还有那几个 API 方法
var postTweet = function(userId, tweetId) {}; // public void postTweet(int userId, int tweetId) {}
var getNewsFeed = function(userId) {}; // public List<Integer> getNewsFeed(int userId) {}
var follow = function(followerId, followeeId) {}; // public void follow(int followerId, int followeeId) {}
var unfollow = function(followerId, followeeId) {}; // public void unfollow(int followerId, int followeeId) {}
之所以要把 Tweet
和 User
类放到 Twitter
类里面,是因为 Tweet
类必须要用到一个全局时间戳 timestamp
,而 User
类又需要用到 Tweet
类记录用户发送的推文,所以它们都作为内部类。不过为了清晰和简洁,下文会把每个内部类和 API 方法单独拿出来实现。
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 = nullptr;
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Tweet:
# 需要传入推文内容(id)和发文时间
def __init__(self, id: int, time: int):
self.id = id
self.time = time
self.next = None
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
type Tweet struct {
id int // 推文内容(id)
time int // 发文时间
next *Tweet
}
// NewTweet initializes a new tweet
// 需要传入推文内容(id)和发文时间
func NewTweet(id int, time int) *Tweet {
return &Tweet{
id: id,
time: time,
next: nil,
}
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var Tweet = function(id, time) {
// 需要传入推文内容(id)和发文时间
this.id = id;
this.time = time;
this.next = null;
}
![](/algo/images/%E8%AE%BE%E8%AE%A1Twitter/tweet.jpg)
User 类的实现
我们根据实际场景想一想,一个用户需要存储的信息有 userId,关注列表,以及该用户发过的推文列表。其中关注列表应该用集合(Hash Set)这种数据结构来存,因为不能重复,而且需要快速查找;推文列表应该由链表这种数据结构储存,以便于进行有序合并的操作。画个图理解一下:
![](/algo/images/%E8%AE%BE%E8%AE%A1Twitter/user.jpg)
除此之外,根据面向对象的设计原则,「关注」「取关」和「发文」应该是 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) {
this->id = userId;
this->head = nullptr;
// 关注一下自己
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 代码对比查看。
timestamp = 0
class Tweet:
def __init__(self, tweetId, timestamp, next=None):
self.tweetId = tweetId
self.timestamp = timestamp
self.next = next
class User:
def __init__(self, userId):
self.id = userId
self.followed = set() # 用户的关注列表
self.head = None # 用户发表的推文链表头结点
self.follow(self.id) # 关注一下自己
def follow(self, userId):
self.followed.add(userId)
def unfollow(self, userId):
if(userId != self.id): # 不可以取关自己
self.followed.discard(userId)
def post(self, tweetId):
global timestamp
twt = Tweet(tweetId, timestamp)
timestamp+=1
twt.next = self.head # 将新建的推文插入链表头,越靠前的推文 time 值越大
self.head = twt
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// Tweet structure
type Tweet struct {
id int
time int
next *Tweet
}
// User structure
type User struct {
id int
// 写文章的人
followed map[int]bool
// 用户发表的推文链表头结点
head *Tweet
}
// 初始化 timestamp 为 0
var timestamp = 0
// New User
func newUser(userId int) *User{
user := &User{}
user.followed = make(map[int]bool)
user.id = userId
user.head = nil
// 关注一下自己
user.follow(user.id)
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)
}
}
// 用户发布一篇Article
func (u *User) post(tweetId int){
t := &Tweet{}
t.id = tweetId
t.time = timestamp
timestamp++
// 将新建的推文插入链表头
// 越靠前的推文 time 值越大
t.next = u.head
u.head = t
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// static int timestamp = 0
var timestamp = 0;
// Class User
var User = function(userId) {
// Private int id;
this.id = userId;
// Public Set<Integer> followed;
this.followed = new Set();
// 用户发表的推文链表头结点
this.head = null;
// Method to follow other users
this.follow = function(userId) {
this.followed.add(userId);
};
// Method to unfollow other users
// 不可以取关自己
this.unfollow = function(userId) {
if (userId !== this.id) {
// Remove the userId from the followed Set
this.followed.delete(userId);
}
};
// Method to post a tweet
this.post = function(tweetId) {
// 新建一个Tweet
var twt = new Tweet(tweetId, timestamp);
timestamp++;
// 将新建的推文插入链表头
// 越靠前的推文 time 值越大
twt.next = this.head;
this.head = twt;
};
// 关注一下自己
this.follow(this.id);
};
几个 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 代码对比查看。
class Twitter {
private:
static int timestamp;
class Tweet {...};
class User {...};
// 我们需要一个映射将 userId 和 User 对象对应起来
unordered_map<int, User> userMap;
public:
// user 发表一条 tweet 动态
void postTweet(int userId, int tweetId) {
// 若 userId 不存在,则新建
if (userMap.find(userId) == userMap.end())
userMap[userId] = User(userId);
User& u = userMap[userId];
u.post(tweetId);
}
// follower 关注 followee
void follow(int followerId, int followeeId) {
// 若 follower 不存在,则新建
if(userMap.find(followerId) == userMap.end()){
User u = User(followerId);
userMap[followerId] = u;
}
// 若 followee 不存在,则新建
if(userMap.find(followeeId) == userMap.end()){
User u = User(followeeId);
userMap[followeeId] = u;
}
userMap[followerId].follow(followeeId);
}
// follower 取关 followee,如果 Id 不存在则什么都不做
void unfollow(int followerId, int followeeId) {
if (userMap.find(followerId) != userMap.end()) {
User& flwer = userMap[followerId];
flwer.unfollow(followeeId);
}
}
// 返回该 user 关注的人(包括他自己)最近的动态 id
// 最多 10 条,而且这些动态必须按从新到旧的时间线顺序排列
vector<int> getNewsFeed(int userId) {
// 需要理解算法,见下文
}
};
int Twitter::timestamp = 0;
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Twitter:
timestamp = 0
class Tweet:
pass
class User:
pass
# 我们需要一个映射将 userId 和 User 对象对应起来
userMap = {}
# user 发表一条 tweet 动态
def postTweet(self, userId: int, tweetId: int) -> None:
# 若 userId 不存在,则新建
if userId not in self.userMap:
self.userMap[userId] = self.User(userId)
u = self.userMap[userId]
u.post(tweetId)
# follower 关注 followee
def follow(self, followerId: int, followeeId: int) -> None:
# 若 follower 不存在,则新建
if followerId not in self.userMap:
u = self.User(followerId)
self.userMap[followerId] = u
# 若 followee 不存在,则新建
if followeeId not in self.userMap:
u = self.User(followeeId)
self.userMap[followeeId] = u
self.userMap[followerId].follow(followeeId)
# follower 取关 followee,如果 Id 不存在则什么都不做
def unfollow(self, followerId: int, followeeId: int) -> None:
if followerId in self.userMap:
flwer = self.userMap[followerId]
flwer.unfollow(followeeId)
# 返回该 user 关注的人(包括他自己)最近的动态 id
# 最多 10 条,而且这些动态必须按从新到旧的时间线顺序排列
def getNewsFeed(self, userId: int) -> List[int]:
# 需要理解算法,见下文
pass
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
type Tweet struct {...}
type User struct {...}
// timestamp 是全局变量
var timestamp int = 0
// 我们需要一个映射将 userId 和 User 对象对应起来
var userMap = make(map[int]*User)
// user 发表一条 tweet 动态
func postTweet(userId int, tweetId int) {
// 若 userId 不存在,则新建
if _, ok := userMap[userId]; !ok {
userMap[userId] = &User{...}
}
u := userMap[userId]
u.post(tweetId)
}
// follow 关注 followee
func follow(followerId int, followeeId int) {
// 若 follower 不存在,则新建
if _, ok := userMap[followerId]; !ok {
u := &User{...}
userMap[followerId] = u
}
// 若 followee 不存在,则新建
if _, ok := userMap[followeeId]; !ok {
u := &User{...}
userMap[followeeId] = u
}
userMap[followerId].follow(followeeId)
}
// follower 取关 followee,如果 Id 不存在则什么都不做
func unfollow(followerId int, followeeId int) {
if _, ok := userMap[followerId]; ok {
flwer := userMap[followerId]
flwer.unfollow(followeeId)
}
}
// 返回该 user 关注的人(包括他自己)最近的动态 id
// 最多 10 条,而且这些动态必须按从新到旧的时间线顺序排列
func getNewsFeed(userId int) []int {
// 需要理解算法,见下文
}
type Twitter struct{...}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var Twitter = function() {
this.timestamp = 0;
this.Tweet = function() {...};
this.User = function() {...};
this.userMap = {};
this.postTweet = function(userId, tweetId) {
if (!this.userMap.hasOwnProperty(userId))
this.userMap[userId] = new this.User(userId);
var u = this.userMap[userId];
u.post(tweetId);
}
this.follow = function(followerId, followeeId) {
if (!this.userMap.hasOwnProperty(followerId)) {
var u = new this.User(followerId);
this.userMap[followerId] = u;
}
if (!this.userMap.hasOwnProperty(followeeId)) {
var u = new this.User(followeeId);
this.userMap[followeeId] = u;
}
this.userMap[followerId].follow(followeeId);
}
this.unfollow = function(followerId, followeeId) {
if (this.userMap.hasOwnProperty(followerId)) {
var flwer = this.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;
// 不在 userMap 中就直接返回
if (userMap.count(userId) == 0) return res;
// 关注列表的用户 Id
set<int> users = userMap[userId].followed;
// 自动通过 time 属性从大到小排序,容量为 users 的大小
priority_queue<Tweet*> pq;
// 先将所有链表头节点插入优先级队列
for (int id : users) {
Tweet* twt = userMap[id].head;
// 排除掉 null 的情况
if (twt == NULL) 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 != NULL)
pq.push(twt->next);
}
return res;
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
import heapq
from typing import List
class Twitter:
# 为了节约篇幅,省略上文给出的代码部分...
def getNewsFeed(self, userId: int) -> List[int]:
res = []
if userId not in userMap: # 如果用户不存在,返回空List
return res
# 关注列表的用户 Id
users = userMap[userId].followed
# 自动通过 time 属性从大到小排序,容量为 users 的大小
pq = [] #采用heapq模块实现优先级队列
# 先将所有链表头节点插入优先级队列
for id in users:
twt = userMap[id].head
if twt is None:
continue
heapq.heappush(pq, (-twt.time, id)) # 采用负值实现大顶堆
while pq:
# 最多返回 10 条就够了
if len(res) == 10:
break
# 弹出 time 值最大的(最近发表的)
time, id = heapq.heappop(pq) # 弹出堆顶元素
res.append(id)
# 将下一篇 Tweet 插入进行排序
if twt.next is not None:
heapq.heappush(pq, (-twt.next.time, twt.next.id))
return res
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
type Twitter struct {
// Omitted code for brevity...
}
func (twt *Twitter) GetNewsFeed(userId int) []int {
res := []int{}
// 关注列表的用户 Id
users, ok := twt.userMap[userId]
if !ok {
return res
}
// 自动通过 time 属性从大到小排序,容量为 users 的大小
pq := make(PriorityQueue, len(users.followed))
// 先将所有链表头节点插入优先级队列
for id := range users.followed {
twt, ok := twt.userMap[id]
if !ok || twt.head == nil {
continue
}
heap.Push(&pq, twt.head)
}
for len(pq) > 0 {
// 最多返回 10 条就够了
if len(res) == 10 {
break
}
// 弹出 time 值最大的(最近发表的)
twt := heap.Pop(&pq).(*Tweet)
res = append(res, twt.id)
// 将下一篇 Tweet 插入进行排序
if twt.next != nil {
heap.Push(&pq, twt.next)
}
}
return res
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var Twitter = function() {
// 为了节约篇幅,省略上文给出的代码部分...
};
Twitter.prototype.getNewsFeed = function(userId) {
// Initialize empty array for news feed
var res = [];
// If the user does not exist in the user map, return an empty array
if(!this.userMap.has(userId)) return res;
// The user Ids from the following list
var users = this.userMap.get(userId).followed;
// Auto sorting by the time property from large to small, capacity is the size of users
// PriorityQueue is not natively available in Javascript, here is an alternative
var pq = new PriorityQueue(users.size, (a, b) => (b.time - a.time));
// First insert all linked list header nodes into the priority queue
for (var id of users) {
var twt = this.userMap.get(id).head;
// If there is no tweet, skip to the next id
if(twt === null) continue;
pq.add(twt);
}
// While the PriorityQueue is not empty
while(!pq.isEmpty()) {
// If already returned 10, break out of the loop
// 最多返回 10 条就够了
if(res.length === 10) break;
// Pop the tweet with the largest time value (most recently published)
// 弹出 time 值最大的(最近发表的)
var twt = pq.poll();
res.push(twt.id);
// If there is next tweet then insert it for sorting
// 将下一篇 Tweet 插入进行排序
if(twt.next !== null)
pq.add(twt.next);
}
return res;
}
这个过程是这样的,下面是我制作的一个 GIF 图描述合并链表的过程。假设有三个 Tweet 链表按 time 属性降序排列,我们把他们降序合并添加到 res 中。注意图中链表节点中的数字是 time 属性,不是 id 属性:
![](/algo/images/%E8%AE%BE%E8%AE%A1Twitter/merge.gif)
至此,这道一个极其简化的 Twitter 时间线功能就设计完毕了,更多数据结构设计相关的题目参见 数据结构设计经典习题。
引用本文的文章
《labuladong 的算法笔记》已经出版,关注公众号查看详情;后台回复「全家桶」可下载配套 PDF 和刷题全家桶:
![](/algo/images/souyisou2.png)