Implement a simple twitter. Support the following method:
postTweet(user_id, tweet_text)
. Post a tweet.getTimeline(user_id)
. Get the given user‘s most recently 10 tweets posted by himself, order by timestamp from most recent to least recent.getNewsFeed(user_id)
. Get the given user‘s most recently 10 tweets in his news feed (posted by his friends and himself). Order by timestamp from most recent to least recent.follow(from_user_id, to_user_id)
. from_user_id followed to_user_id.unfollow(from_user_id, to_user_id)
. from_user_id unfollowed to to_user_id.postTweet(1, "LintCode is Good!!!") >> 1 getNewsFeed(1) >> [1] getTimeline(1) >> [1] follow(2, 1) getNewsFeed(2) >> [1] unfollow(2, 1) getNewsFeed(2) >> []
分析:
用 HashMap<Integer, HashSet<Integer>> 来保持user和他follow的id。 找出最新tweets的时候,从末到头查就可以了。
/** * Definition of Tweet: * public class Tweet { * public int id; * public int user_id; * public String text; * public static Tweet create(int user_id, String tweet_text) { * // This will create a new tweet object, * // and auto fill id * } * } */ public class MiniTwitter { private ArrayList<Tweet> list; private HashMap<Integer, HashSet<Integer>> followers; public MiniTwitter() { // initialize your data structure here. list = new ArrayList<Tweet>(); followers = new HashMap<Integer, HashSet<Integer>>(); } // @param user_id an integer // @param tweet a string // return a tweet public Tweet postTweet(int user_id, String tweet_text) { Tweet t = Tweet.create(user_id, tweet_text); list.add(t); return t; } // @param user_id an integer // return a list of 10 new feeds recently // and sort by timeline public List<Tweet> getNewsFeed(int user_id) { // Write your code here List<Tweet> tList = new ArrayList<Tweet>(); for (int i = list.size() - 1; i >= 0; i--) { Tweet t = list.get(i); if (t.user_id == user_id || isFollower(user_id, t.user_id)) { tList.add(t); if (tList.size() == 10) { break; } } } return tList; } public boolean isFollower(int from, int to) { if (followers.containsKey(from)) { return followers.get(from).contains(to); } return false; } // @param user_id an integer // return a list of 10 new posts recently // and sort by timeline public List<Tweet> getTimeline(int user_id) { // Write your code here List<Tweet> tList = new ArrayList<Tweet>(); for (int i = list.size() - 1; i >= 0; i--) { Tweet t = list.get(i); if (t.user_id == user_id) { tList.add(t); if (tList.size() == 10) { break; } } } return tList; } // @param from_user_id an integer // @param to_user_id an integer // from user_id follows to_user_id public void follow(int from_user_id, int to_user_id) { // Write your code here if (followers.containsKey(from_user_id)) { followers.get(from_user_id).add(to_user_id); } else { followers.put(from_user_id, new HashSet<Integer>()); follow(from_user_id, to_user_id); } } // @param from_user_id an integer // @param to_user_id an integer // from user_id unfollows to_user_id public void unfollow(int from_user_id, int to_user_id) { if (followers.containsKey(from_user_id)) { followers.get(from_user_id).remove(to_user_id); } } }
原文:http://www.cnblogs.com/beiyeqingteng/p/5665522.html