🌕🌕 355. 设计推特

难度: 🌕🌕

问题描述

---

解法

class Twitter {
    // 思路：
    // 构造节点类，添加时间戳属性，保证时间顺序
    // 如何获取当前用户的最近 10 条推特？
    // 需要获取当前用户关注了哪些用户 - map
    // 将 自己 & 关注的用户 的推特链表按照 时间戳 降序取 10 条 --> PriorityQueue

    HashMap<Integer, HashSet<Integer>> map; // userId - set
    HashMap<Integer, Node> pmap; // userId - twitters 最近一条节点
    int timestamp; // 时间戳

    public Twitter() {
        map = new HashMap<>();
        pmap = new HashMap<>();
        this.timestamp = 0;
    }
    
    public void postTweet(int userId, int tweetId) {
        timestamp ++;
        Node cur = new Node(tweetId, timestamp); // 当前推特
        if(!pmap.containsKey(userId)) {
            // 这时当前用户发表的第一条推特
            pmap.put(userId, cur);
        } else {
            Node pre = pmap.get(userId); // 获取该用户之前发布的最新的推特节点
            cur.next = pre;
            pmap.put(userId, cur);
        }
    }
    
    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> {
            return b.timestamp - a.timestamp; 
        }); // 时间戳降序，时间戳越大，表示推特越新
        List<Integer> res = new ArrayList<>();

        if(pmap.containsKey(userId)) {
            queue.offer(pmap.get(userId)); // 如果自己发布过推特
        }
        if(map.containsKey(userId)) {
            // 说明自己还关注了其他人
            HashSet<Integer> set = map.get(userId);
            // 遍历，如果关注的用户也发表过推特，加入比较队列
            for(int i: set) {
                if(pmap.containsKey(i)) {
                    queue.offer(pmap.get(i));
                }
            }
        }
        // 从队列中取出最多 10 条推特
        int count = 0;
        while(!queue.isEmpty() && count < 10) {
            Node cur = queue.poll(); // 是所有相关用户发布的推特中最新的一条
            res.add(cur.tweetId);
            count ++;
            // 判断最新一条对应的用户是否有后续推特，如果有，入队
            if(cur.next != null) {
                queue.offer(cur.next);
            }
        }
        return res;
    }
    
    public void follow(int followerId, int followeeId) {
        if(followerId == followeeId) {
            return; // 自己关注自己，没意思，跳
        }
        if(!map.containsKey(followerId)) {
            // 说明该用户之前没有关注过任何人
            HashSet<Integer> set = new HashSet<>();
            set.add(followeeId);
            map.put(followerId, set);
        } else {
            HashSet<Integer> set = map.get(followerId);
            set.add(followeeId);
            map.put(followerId, set);
        }
    }
    
    public void unfollow(int followerId, int followeeId) {
        if(followerId == followeeId) {
            return;
        }
        if(!map.containsKey(followerId)) {
            return;
        }
        HashSet<Integer> set = map.get(followerId);
        set.remove(followeeId);
        map.put(followerId, set);
    }
}

class Node {
    int tweetId;
    int timestamp;
    Node next;
    public Node(int tweetId, int timestamp) {
        this.tweetId = tweetId;
        this.timestamp = timestamp;
    }
}

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

---

输出