提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章来源:https://www.toymoban.com/news/detail-810388.html
前言
力扣第 355 「设计推特」不仅题目本身很有意思,而且把合并多个有序链表的算法和面向对象设计(OO design)结合起来了,很有实际意义
文章来源地址https://www.toymoban.com/news/detail-810388.html
一、力扣355. 设计推特
class Twitter {
// 全局时间戳
int globalTime = 0;
// 记录用户 ID 到用户示例的映射
HashMap<Integer, User> idToUser = new HashMap<>();
// Tweet 类
class Tweet {
private int id;
// 时间戳用于对信息流按照时间排序
private int timestamp;
// 指向下一条 tweet,类似单链表结构
private Tweet next;
public Tweet(int id) {
this.id = id;
// 新建一条 tweet 时记录并更新时间戳
this.timestamp = globalTime++;
}
public int getId() {
return id;
}
public int getTimestamp() {
return timestamp;
}
public Tweet getNext() {
return next;
}
public void setNext(Tweet next) {
this.next = next;
}
}
// 用户类
class User {
// 记录该用户的 id 以及发布的 tweet
private int id;
private Tweet tweetHead;
// 记录该用户的关注者
private HashSet<User> followedUserSet;
public User(int id) {
this.id = id;
this.tweetHead = null;
this.followedUserSet = new HashSet<>();
}
public int getId() {
return id;
}
public Tweet getTweetHead() {
return tweetHead;
}
public HashSet<User> getFollowedUserSet() {
return followedUserSet;
}
public boolean equals(User other) {
return this.id == other.id;
}
// 关注其他人
public void follow(User other) {
followedUserSet.add(other);
}
// 取关其他人
public void unfollow(User other) {
followedUserSet.remove(other);
}
// 发布一条 tweet
public void post(Tweet tweet) {
// 把新发布的 tweet 作为链表头节点
tweet.setNext(tweetHead);
tweetHead = tweet;
}
}
public void postTweet(int userId, int tweetId) {
// 如果这个用户还不存在,新建用户
if (!idToUser.containsKey(userId)) {
idToUser.put(userId, new User(userId));
}
User user = idToUser.get(userId);
user.post(new Tweet(tweetId));
}
public List<Integer> getNewsFeed(int userId) {
List<Integer> res = new LinkedList<>();
if (!idToUser.containsKey(userId)) {
return res;
}
// 获取该用户关注的用户列表
User user = idToUser.get(userId);
Set<User> followedUserSet = user.getFollowedUserSet();
// 每个用户的 tweet 是一条按时间排序的链表
// 现在执行合并多条有序链表的逻辑,找出时间线中的最近 10 条动态
PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> {
// 按照每条 tweet 的发布时间降序排序(最近发布的排在事件流前面)
return b.timestamp - a.timestamp;
});
// 该用户自己的 tweet 也在时间线内
if (user.getTweetHead() != null) {
pq.offer(user.getTweetHead());
}
for (User other : followedUserSet) {
if (other.getTweetHead() != null) {
pq.offer(other.tweetHead);
}
}
// 合并多条有序链表
int count = 0;
while (!pq.isEmpty() && count < 10) {
Tweet tweet = pq.poll();
res.add(tweet.getId());
if (tweet.getNext() != null) {
pq.offer(tweet.getNext());
}
count++;
}
return res;
}
public void follow(int followerId, int followeeId) {
// 如果用户还不存在,则新建用户
if (!idToUser.containsKey(followerId)) {
idToUser.put(followerId, new User(followerId));
}
if (!idToUser.containsKey(followeeId)) {
idToUser.put(followeeId, new User(followeeId));
}
User follower = idToUser.get(followerId);
User followee = idToUser.get(followeeId);
// 关注者关注被关注者
follower.follow(followee);
}
public void unfollow(int followerId, int followeeId) {
if (!idToUser.containsKey(followerId) || !idToUser.containsKey(followeeId)) {
return;
}
User follower = idToUser.get(followerId);
User followee = idToUser.get(followeeId);
// 关注者取关被关注者
follower.unfollow(followee);
}
}
到了这里,关于力扣labuladong——一刷day96的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!