Leetcode: Design Twitter
LeetCode Design twitter
2023-09-11 14:14:07 时间
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);
注意需要maintain一个time stamp, 每次postTweet时++。还有要注意unfollow的时候,不能unfollow自己
1 public class Twitter { 2 class User { 3 int userId; 4 List<Tweet> tweets; 5 Set<Integer> followees; 6 public User(int id) { 7 this.userId = id; 8 this.tweets = new ArrayList<Tweet>(); 9 this.followees = new HashSet<Integer>(); 10 followees.add(id); 11 } 12 } 13 14 class Tweet { 15 int tweetId; 16 int seq; 17 public Tweet(int id, int num) { 18 this.tweetId = id; 19 this.seq = num; 20 } 21 } 22 23 Map<Integer, User> userMap; 24 PriorityQueue<Tweet> maxHeap; 25 int seq; 26 27 /** Initialize your data structure here. */ 28 public Twitter() { 29 userMap = new HashMap<Integer, User>(); 30 maxHeap = new PriorityQueue<Tweet>(11, new Comparator<Tweet>() { 31 public int compare(Tweet t1, Tweet t2) { 32 return t2.seq-t1.seq; 33 } 34 }); 35 this.seq = 0; 36 } 37 38 /** Compose a new tweet. */ 39 public void postTweet(int userId, int tweetId) { 40 if (!userMap.containsKey(userId)) { 41 User newUser = new User(userId); 42 userMap.put(userId, newUser); 43 } 44 User curUser = userMap.get(userId); 45 curUser.tweets.add(new Tweet(tweetId, ++this.seq)); 46 } 47 48 /** 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. */ 49 public List<Integer> getNewsFeed(int userId) { 50 List<Integer> res = new ArrayList<Integer>(); 51 if (!userMap.containsKey(userId)) return res; 52 User curUser = userMap.get(userId); 53 maxHeap.clear(); 54 for (int followeeId : curUser.followees) { 55 List<Tweet> followeeTweets = userMap.get(followeeId).tweets; 56 for (Tweet tweet : followeeTweets) { 57 maxHeap.offer(tweet); 58 } 59 } 60 for (int i=0; i<10 && !maxHeap.isEmpty(); i++) { 61 res.add(maxHeap.poll().tweetId); 62 } 63 return res; 64 } 65 66 /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ 67 public void follow(int followerId, int followeeId) { 68 if (!userMap.containsKey(followerId)) { 69 User newUser = new User(followerId); 70 userMap.put(followerId, newUser); 71 } 72 if (!userMap.containsKey(followeeId)) { 73 User newUser = new User(followeeId); 74 userMap.put(followeeId, newUser); 75 } 76 userMap.get(followerId).followees.add(followeeId); 77 } 78 79 /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ 80 public void unfollow(int followerId, int followeeId) { 81 if (!userMap.containsKey(followerId)) { 82 User newUser = new User(followerId); 83 userMap.put(followerId, newUser); 84 } 85 if (!userMap.containsKey(followeeId)) { 86 User newUser = new User(followeeId); 87 userMap.put(followeeId, newUser); 88 } 89 if (followerId != followeeId) 90 userMap.get(followerId).followees.remove(followeeId); 91 } 92 } 93 94 /** 95 * Your Twitter object will be instantiated and called as such: 96 * Twitter obj = new Twitter(); 97 * obj.postTweet(userId,tweetId); 98 * List<Integer> param_2 = obj.getNewsFeed(userId); 99 * obj.follow(followerId,followeeId); 100 * obj.unfollow(followerId,followeeId); 101 */
关于PriorityQueue还看到这一种写法,挺简单的:
1 Set<Integer> users = userMap.get(userId).followed;
2 PriorityQueue<Tweet> q = new PriorityQueue<Tweet>(users.size(), (a,b)->(b.time-a.time));
相关文章
- Java实现 LeetCode 777 在LR字符串中交换相邻字符(分析题)
- Java实现 LeetCode 690 员工的重要性(简易递归)
- Java实现 LeetCode 488 祖玛游戏
- Java实现 LeetCode 315 计算右侧小于当前元素的个数
- Java实现 LeetCode 152 乘积最大子序列
- Java实现 LeetCode 109 有序链表转换二叉搜索树
- Java实现 LeetCode 66 加一
- Java实现LeetCode_0009_PalindromeNumber
- LeetCode(100):相同的树
- 【LeetCode Python实现】 5474. 好叶子节点对的数量(中等)
- 【LeetCode Python实现】635. 设计日志存储系统(中等)
- Leetcode 81. 搜索旋转排序数组 II
- Leetcode 1534. 统计好三元组
- Leetcode 703. 数据流中的第 K 大元素(终于解决)
- Leetcode 521. 最长特殊序列 Ⅰ(不知道考察啥)
- LeetCode:Find Minimum in Rotated Sorted Array
- leetcode 172. Factorial Trailing Zeroes
- leetcode 35. Search Insert Position
- LeetCode 217. 存在重复元素
- 【LeetCode】264.丑数II
- 多因素deseq2 formula 怎么理解 如何设置design 哈佛大学——差异表达分析(七)设计公式(Design formulas)多因素差异分析 多个影响因子会影响差异分析结果 多因子