摘要：思路和代碼這道題目本質(zhì)上是考察是否能將數(shù)據(jù)結(jié)構(gòu)的知識(shí)靈活的運(yùn)用于現(xiàn)實(shí)生活中。這題等價(jià)于我們每次都會(huì)比較當(dāng)前所有被關(guān)注者發(fā)布的最新未讀，選出結(jié)果后將其插入結(jié)果集。

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user"s news feed. Your design should support the following methods:

postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(userId): 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.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.
Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1"s news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1"s news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1"s news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

設(shè)計(jì)一個(gè)迷你推特，要求能夠支持以下幾個(gè)方法：發(fā)布推特，關(guān)注用戶，取關(guān)用戶，查看最近的十條關(guān)注用戶發(fā)送的推特。

這道題目本質(zhì)上是考察是否能將數(shù)據(jù)結(jié)構(gòu)的知識(shí)靈活的運(yùn)用于現(xiàn)實(shí)生活中。從最直觀的想法來看，我們會(huì)有一個(gè)用戶實(shí)體，每個(gè)用戶會(huì)記錄自己關(guān)注的用戶的id，以及記錄自己發(fā)表的所有tweet。這里唯一的難點(diǎn)在于我們?nèi)绾伟凑諘r(shí)間順序獲取tweet流。

這么一想，這題其實(shí)就轉(zhuǎn)換為如何將N個(gè)有序排列的數(shù)組匯合成一個(gè)有序的數(shù)組。這題等價(jià)于我們每次都會(huì)比較當(dāng)前所有被關(guān)注者發(fā)布的最新未讀tweet，選出結(jié)果后將其插入結(jié)果集。這里我們可以利用等價(jià)隊(duì)列幫助我們更快的完成選擇的過程。

public class Twitter {

    
    public Twitter() {
        users = new HashMap<>();
    }
    
    public static int timestamp = 0;
    private Map users;
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if(!users.containsKey(userId)) {
            User user = new User(userId);
            users.put(userId, user);
        }
        
        User user = users.get(userId);
        user.tweet(tweetId);
    }
    
    /** 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 getNewsFeed(int userId) {
        List result = new ArrayList();
        if(!users.containsKey(userId)) {
            return result;
        }
        User user = users.get(userId);
        
        PriorityQueue queue = new PriorityQueue<>(user.followed.size());
        for(int followee : user.followed) {
            User tmp = users.get(followee);
            if(tmp != null && tmp.headTweet != null) {
                queue.offer(tmp.headTweet);
            } 
        }
        
        while(!queue.isEmpty() && result.size() < 10) {
            Tweet t = queue.poll();
            result.add(t.tweetId);
            if(t.next != null) {
                queue.offer(t.next);
            }
        }
        return result;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if(!users.containsKey(followerId)) {
            User user = new User(followerId);
            users.put(followerId, user);
        }
        if(!users.containsKey(followeeId)) {
            User user = new User(followeeId);
            users.put(followeeId, user);
        }
        
        User user = users.get(followerId);
        user.follow(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if(!users.containsKey(followerId) || followerId == followeeId) {
            return;
        }
      
        
        User user = users.get(followerId);
        user.unfollow(followeeId);
    }
    
    public static class User{
        
        int userId;
        
        Set followed;
        
        Tweet headTweet;
        
        public User(int userId) {
            this.userId = userId;
            this.followed = new HashSet<>();
            follow(userId);
        }
        
        public void follow(int userId) {
            followed.add(userId);
        }
        
        public void unfollow(int userId) {
            followed.remove(userId);
        }
        
        public void tweet(int tweetId) {
            Tweet tweet = new Tweet(tweetId);
            tweet.next = headTweet;
            headTweet = tweet;
        }
        
    }
    
    public static class Tweet implements Comparable{
        
        int tweetId;
        
        Tweet next;
        
        int time;
        
        public Tweet(int tweetId) {
            this.tweetId = tweetId;
            this.time = timestamp++;
        }

        @Override
        public int compareTo(Tweet o) {
            return o.time - this.time;
        }
    }
}