LeetCode355-设计推特

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/design-twitter/

中文链接：https://leetcode-cn.com/problems/design-twitter/

题目详述

设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：

  1. postTweet(userId, tweetId): 创建一条新的推文
  2. getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
  3. follow(followerId, followeeId): 关注一个用户
  4. unfollow(followerId, followeeId): 取消关注一个用户

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Twitter twitter = new Twitter();

// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
twitter.postTweet(1, 5);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
twitter.getNewsFeed(1);

// 用户1关注了用户2.
twitter.follow(1, 2);

// 用户2发送了一个新推文 (推文id = 6).
twitter.postTweet(2, 6);

// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].
// 推文id6应当在推文id5之前，因为它是在5之后发送的.
twitter.getNewsFeed(1);

// 用户1取消关注了用户2.
twitter.unfollow(1, 2);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
// 因为用户1已经不再关注用户2.
twitter.getNewsFeed(1);

题目详解

  • 首先构建一个类 Data，包含 id、tweetId 两个字段，id 越大，推文越新。
  • 用 Map<Integer, List<Data>> posts 表示从一个用户映射到他发布的推文列表。
  • 用 Map<Integer, Set<Integer>> follows 表示从一个用户映射到他的关注列表。

对于以下操作：

  1. postTweet(userId, tweetId)，首先用 posts 找到这个用户发布的推特列表，然后将 tweetId 插入该列表中。
  2. getNewsFeed(userId)，首先用 follows 找到这个用户所有的关注，然后将他们发布的所有微博存入一个优先队列（可以采用大顶堆，也可以采用小顶堆，采用小顶堆取出时要逆序），最后取出最近的十条推文。
  3. follow(followerId, followeeId)，首先用 follows 找到 followerId 的关注列表，然后将 followeeId 插入该列表。
  4. unfollow(followerId, followeeId)，首先用 follows 找到 followerId 的关注列表，然后将 followeeId 从该列表中删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class LeetCode_00355 {

    class Twitter {
        class Data {
            int id, tweetId;

            public Data(int id, int tweetId) {
                this.id = id;
                this.tweetId = tweetId;
            }
        }

        private Map<Integer, List<Data>> posts;
        private Map<Integer, Set<Integer>> follows;
        private int id;

        /** Initialize your data structure here. */
        public Twitter() {
            posts = new HashMap<>();
            follows = new HashMap<>();
            id = 0;
        }

        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            if (!posts.containsKey(userId)) {
                posts.put(userId, new ArrayList<>());
            }
            posts.get(userId).add(new Data(id++, 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<Integer> getNewsFeed(int userId) {
//            List<Data> list = new ArrayList<>();
//            List<Data> ps = posts.get(userId);
//            if (ps != null) {
//                for (Data data : ps) {
//                    list.add(data);
//                }
//            }
//            Set<Integer> fs = follows.get(userId);
//            if (fs != null) {
//                for (int f : fs) {
//                    ps = posts.get(f);
//                    if (ps != null) {
//                        for (Data data : ps) {
//                            list.add(data);
//                        }
//                    }
//                }
//            }
//            list.sort(new Comparator<Data>() {
//                @Override
//                public int compare(Data o1, Data o2) {
//                    return Integer.compare(o2.id, o1.id);
//                }
//            });
//            List<Integer> res = new ArrayList<>();
//            for (int i = 0; i < 10 && i < list.size(); ++i) {
//                res.add(list.get(i).tweetId);
//            }
//            return res;
//        }

        public List<Integer> getNewsFeed(int userId) {
            PriorityQueue<Data> queue = new PriorityQueue<>(10, new Comparator<Data>() {
                @Override
                public int compare(Data o1, Data o2) {
                    return Integer.compare(o2.id, o1.id);
                }
            });
            List<Data> ps = posts.get(userId);
            if (ps != null) {
                for (Data data : ps) {
                    queue.offer(data);
                }
            }
            Set<Integer> fs = follows.get(userId);
            if (fs != null) {
                for (int f : fs) {
                    ps = posts.get(f);
                    if (ps != null) {
                        for (Data data : ps) {
                            queue.offer(data);
                        }
                    }
                }
            }
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < 10 && !queue.isEmpty(); ++i) {
                res.add(queue.poll().tweetId);
            }
            return res;
        }

        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        public void follow(int followerId, int followeeId) {
            if (followerId != followeeId) {
                if (!follows.containsKey(followerId)) {
                    follows.put(followerId, new HashSet<>());
                }
                follows.get(followerId).add(followeeId);
            }
        }

        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        public void unfollow(int followerId, int followeeId) {
            if (follows.containsKey(followerId)) {
                follows.get(followerId).remove(followeeId);
            }
        }
    }
}