摘要：的想法就是用每次得到最小的鏈表頭的值，輸出。每個(gè)都有一個(gè)關(guān)注人列表，用儲(chǔ)存。用戶(hù)可以發(fā)消息，關(guān)注別人，取消關(guān)注別人。可以系統(tǒng)得到關(guān)注人的消息合集，這個(gè)方法必須在這個(gè)層級(jí)。因?yàn)橛脩?hù)只知道自己的信息。

Merge k Sorted Lists

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null) return null;
        // O(k) construct heap, m*logk do iterate,  Space O(k)
        // lamda expression is super slow 99ms vs 26ms Comparator
        // PriorityQueue pq = new PriorityQueue((a,b) -> (a.val-b.val));
        PriorityQueue pq = new PriorityQueue(new Comparator(){
            @Override
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
        });
        
        for(ListNode l:lists) {
            if(l != null) pq.offer(l);
        }
        // every new list need a dummy node
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while(!pq.isEmpty()){
            ListNode cur = pq.poll();
            pre.next = cur;
            if(cur.next != null) pq.offer(cur.next);
            pre = pre.next;
        }
        
        return dummy.next;
    }
}

Merge k Sorted Lists的想法就是用PriorityQueue每次得到最小的鏈表頭的值，輸出。如果next!=null,繼續(xù)放到PriorityQueue里。
Twitter 本質(zhì)上就是一個(gè)消息列表，按時(shí)間順序從關(guān)注人列表里得到他們的tweets并整合顯示。
每個(gè)user都有一個(gè)關(guān)注人列表，用hashset儲(chǔ)存。還有一個(gè)tweets消息列表，這里按時(shí)間線(xiàn)就已經(jīng)形成一個(gè)Sorted List.
一個(gè)user要得到最新的tweets, 首先找到關(guān)注人，把他們的tweets消息列表存到PriorityQueue里，就變成了Merge k Sorted Lists.

這里用OOD是因?yàn)楦咏F(xiàn)實(shí)情況。twitter就是一個(gè)用戶(hù)看到關(guān)注人消息集合的媒體。
基本的entity就是消息tweets和用戶(hù)user。
tweets要體現(xiàn)出時(shí)間線(xiàn)，就要模擬linkedlist。
user用戶(hù)可以發(fā)消息，關(guān)注別人，取消關(guān)注別人。
user可以twitter系統(tǒng)得到關(guān)注人的消息合集，這個(gè)方法必須在twitter這個(gè)層級(jí)。因?yàn)橛脩?hù)只知道自己的信息。

public class Twitter {
    private static int timestamp = 0;
    
    private Map userMap;
    
    class Tweet{
        public int id;
        public int time;
        public Tweet next;
        
        public Tweet(int id) {
            this.id = id;
            time = timestamp++;
            next = null;
        }
    }
    
    public class User{
        public int id;
        public Set followed;
        public Tweet tweet_head;
        
        public User(int id) {
            this.id = id;
            followed = new HashSet();
            follow(id);
            tweet_head = null;
        }
        
        public void follow(int id) {
            followed.add(id);
        }
        
        public void unfollow(int id){
            followed.remove(id);
        }
        
        public void post(int id){
            Tweet tweet = new Tweet(id);
            tweet.next = tweet_head;
            tweet_head = tweet;
        }
    }
    
    
    
    /** Initialize your data structure here. */
    public Twitter() {
        userMap = new HashMap();
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if(!userMap.containsKey(userId)){
            User u = new User(userId);
            userMap.put(userId, u);
        }
        userMap.get(userId).post(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 news = new LinkedList<>();
        if(!userMap.containsKey(userId)){
            return news;
        }
        
        Set users = userMap.get(userId).followed;
        PriorityQueue pq = new PriorityQueue(users.size(), (a,b) -> (b.time - a.time));
        for(int u:users){
            Tweet t = userMap.get(u).tweet_head;
            if(t != null)  {
                pq.offer(t);
            }
        }
        
        int n = 0;
        while(!pq.isEmpty() && n < 10) {
            Tweet t = pq.poll();
            news.add(t.id);
            if(t.next != null) {
                pq.offer(t.next);
            }
            n++;
        }
        
        return news;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if(!userMap.containsKey(followerId)){
            User u = new User(followerId);
            userMap.put(followerId, u);
        }
        if(!userMap.containsKey(followeeId)){
            User u = new User(followeeId);
            userMap.put(followeeId, u);
        }
        userMap.get(followerId).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(!userMap.containsKey(followerId) || followerId == followeeId){
            return;
        }
        userMap.get(followerId).unfollow(followeeId);
    }
}

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);
 */