难度 中等
这道题虽然是中等，但是完成的时间跟大多数简单差不太多，以至于今天荒废了一天还能在一天过去之前把卡打了。可能因为刚好不在我的知识盲区，不过执行时间不是很理想，继续优化对我的帮助不大，所以就这样了。看了下效率更好的算法，大概就是在检索推文的时候先建立一个列表，把自己和自己关注的人的推文（所以要求推文列表也用哈希表）都加入该列表，然后取出十个。我的推文列表用List，直接遍历的，效率会差一些。
class Twitter {
public class TwitterMsg{
public TwitterMsg(int uId, int tId){
userId = uId;
tweetId = tId;
}
public int userId;
public int tweetId;
}
ArrayList<TwitterMsg> msgList = new ArrayList<TwitterMsg>();
HashMap<Integer, HashMap<Integer, Integer>> followMap = new HashMap<Integer, HashMap<Integer, Integer>>();
/** Initialize your data structure here. */
public Twitter() {
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
TwitterMsg msg = new TwitterMsg(userId, tweetId);
msgList.add(msg);
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
public List<Integer> getNewsFeed(int userId) {
List<Integer> resultList = new ArrayList<Integer>();
if(msgList.size() < 1){
return resultList;
}
int count = 0;
for(int i = msgList.size()-1; i >= 0; i--){
if(count == 10){
break;
}
TwitterMsg msg = msgList.get(i);
if(msg != null && msg.userId == userId){
resultList.add(msg.tweetId);
count++;
}else if(followMap.containsKey(userId) && followMap.get(userId).containsKey(msg.userId)){
resultList.add(msg.tweetId);
count++;
}
}
return resultList;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
HashMap followees = new HashMap<Integer, Integer>();
if(followMap.containsKey(followerId)){
followees = followMap.get(followerId);
followees.put(followeeId, 1);
}else{
followees.put(followeeId, 1);
followMap.put(followerId, followees);
}
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
if(followMap.containsKey(followerId)){
HashMap followees = followMap.get(followerId);
if(followees.containsKey(followeeId)){
followees.remove(followeeId);
}
}
}
}
