【355设计推特】
前言题目源码
前言
好难，今天的题目在数据结构上的设计好难，可能还是自己菜，解析看了好一会，不过当数据结构确定后，整个难点在获取前十条推文，使用一个链表记录每个人的推文，获取前十条就是根据时间戳合并链表。
题目
官方题目
源码
class Twitter {
private class Node{
Set
<Integer>followee
;
LinkedList
<Integer>tweet
;
Node(){
followee
=new HashSet<Integer>();
tweet
=new LinkedList<Integer>();
}
}
private int maxTweet
,time
;
private Map
<Integer,Integer> tweetTime
;
private Map
<Integer,Node>user
;
public Twitter() {
maxTweet
=10;
time
=0;
tweetTime
=new HashMap<Integer,Integer>();
user
=new HashMap<Integer,Node>();
}
public void init(int userId
){
user
.put(userId
,new Node());
}
public void postTweet(int userId
, int tweetId
) {
if (!user
.containsKey(userId
)){
init(userId
);
}
if (user
.get(userId
).tweet
.size()==maxTweet
){
user
.get(userId
).tweet
.remove(maxTweet
-1);
}
user
.get(userId
).tweet
.addFirst(tweetId
);
tweetTime
.put(tweetId
,++time
);
}
public List
<Integer> getNewsFeed(int userId
) {
LinkedList
<Integer> ans
=new LinkedList<Integer>();
for (int it
:user
.getOrDefault(userId
,new Node()).tweet
){
ans
.addLast(it
);
}
for (int followId
:user
.getOrDefault(userId
,new Node()).followee
){
if(followId
==userId
){
continue;
}
LinkedList
<Integer> res
=new LinkedList<Integer>();
int tweetSize
=user
.get(followId
).tweet
.size();
Iterator
<Integer> it
=user
.get(followId
).tweet
.iterator();
int i
=0,j
=0,cur
=-1;
if(j
<tweetSize
){
cur
=it
.next();
while(i
<ans
.size() && j
<tweetSize
){
if(tweetTime
.get(cur
)>tweetTime
.get(ans
.get(i
))){
res
.addLast(cur
);
++j
;
if(it
.hasNext()){
cur
=it
.next();
}
}else{
res
.addLast(ans
.get(i
));
++i
;
}
if (res
.size()==maxTweet
){
break;
}
}
}
for(;i
<ans
.size() && res
.size()<maxTweet
;++i
){
res
.addLast(ans
.get(i
));
}
if(j
<tweetSize
&& res
.size()<maxTweet
){
res
.addLast(cur
);
for (;it
.hasNext()&& res
.size()<maxTweet
;){
res
.addLast(it
.next());
}
}
ans
=new LinkedList<Integer>(res
);
}
return ans
;
}
public void follow(int followerId
, int followeeId
) {
if(!user
.containsKey(followerId
)){
init(followerId
);
}
if(!user
.containsKey(followeeId
)){
init(followeeId
);
}
user
.get(followerId
).followee
.add(followeeId
);
}
public void unfollow(int followerId
, int followeeId
) {
user
.getOrDefault(followerId
,new Node()).followee
.remove(followeeId
);
}
}
Processed:
0.008, SQL:
10
