友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
355. 设计推特
设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。
实现 Twitter 类：
-
Twitter()初始化简易版推特对象 -
void postTweet(int userId, int tweetId)根据给定的tweetId和userId创建一条新推文。每次调用此函数都会使用一个不同的tweetId。 -
List<Integer> getNewsFeed(int userId)检索当前用户新闻推送中最近10条推文的 ID。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。 -
void follow(int followerId, int followeeId)ID 为followerId的用户开始关注 ID 为followeeId的用户。 -
void unfollow(int followerId, int followeeId)ID 为followerId的用户不再关注 ID 为followeeId的用户。
示例：
输入 ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]] 输出 [null, null, [5], null, null, [6, 5], null, [5]] 解释 Twitter twitter = new Twitter(); twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5) twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文 twitter.follow(1, 2); // 用户 1 关注了用户 2 twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6) twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的 twitter.unfollow(1, 2); // 用户 1 取消关注了用户 2 twitter.getNewsFeed(1); // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2
提示：
-
1 <= userId, followerId, followeeId <= 500 -
0 <= tweetId <= 104 -
所有推特的 ID 都互不相同
-
postTweet、getNewsFeed、follow和unfollow方法最多调用3 * 104次
思路分析
由于用户最多可以看到 10 条 Tweet，可以查看自己和关注人的 Tweet，并且按照时间倒序排列。那么，可以使用 List 存 Tweet。当用户超过 10 条时，删除最早的 Tweet。用户查看时，从后向前遍历，找出 10 条符合条件的 Tweet 即可。
还可以按照另外一个思路：对每个用户存一个 List，然后当用户查看 Tweet 时，利用多路归并+优先队列筛选出最新发布的 10 条 Tweet。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-07-17 22:34:01
*/
class Twitter {
// 关注列表
Map<Integer, Set<Integer>> follower;
// 被谁关注
Map<Integer, Set<Integer>> followee;
List<Tweet> tweets;
Map<Integer, Integer> count;
public Twitter() {
follower = new HashMap<>();
followee = new HashMap<>();
tweets = new ArrayList<>();
count = new HashMap<>();
}
public void postTweet(int userId, int tweetId) {
tweets.add(new Tweet(userId, tweetId));
Integer oriCnt = count.getOrDefault(userId, 0);
if (oriCnt >= 10) {
for (int i = 0; i < tweets.size(); i++) {
Tweet tweet = tweets.get(i);
if (tweet.owner == userId) {
tweets.remove(i);
break;
}
}
} else {
int cnt = oriCnt + 1;
count.put(userId, cnt);
}
}
public List<Integer> getNewsFeed(int userId) {
List<Integer> result = new ArrayList<>();
for (int i = tweets.size() - 1; i >= 0; i--) {
Tweet tweet = tweets.get(i);
if (tweet.owner == userId
|| follower.getOrDefault(userId, Collections.emptySet()).contains(tweet.owner)) {
result.add(tweet.tweet);
}
if (result.size() == 10) {
break;
}
}
return result;
}
public void follow(int followerId, int followeeId) {
if (followerId == followeeId) {
return;
}
follower.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
followee.computeIfAbsent(followeeId, k -> new HashSet<>()).add(followerId);
}
public void unfollow(int followerId, int followeeId) {
if (followerId == followeeId) {
return;
}
Set<Integer> followers = follower.get(followerId);
if (followers != null) {
followers.remove(followeeId);
}
Set<Integer> followees = followee.get(followeeId);
if (followees != null) {
followees.remove(followerId);
}
}
private static class Tweet {
int owner;
int tweet;
public Tweet(int owner, int tweet) {
this.owner = owner;
this.tweet = tweet;
}
}
}