摘要:思路和代碼這道題目本質上是考察是否能將數據結構的知識靈活的運用于現實生活中。這題等價于我們每次都會比較當前所有被關注者發布的最新未讀,選出結果后將其插入結果集。
題目要求
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);
設計一個迷你推特,要求能夠支持以下幾個方法:發布推特,關注用戶,取關用戶,查看最近的十條關注用戶發送的推特。
思路和代碼這道題目本質上是考察是否能將數據結構的知識靈活的運用于現實生活中。從最直觀的想法來看,我們會有一個用戶實體,每個用戶會記錄自己關注的用戶的id,以及記錄自己發表的所有tweet。這里唯一的難點在于我們如何按照時間順序獲取tweet流。
這么一想,這題其實就轉換為如何將N個有序排列的數組匯合成一個有序的數組。這題等價于我們每次都會比較當前所有被關注者發布的最新未讀tweet,選出結果后將其插入結果集。這里我們可以利用等價隊列幫助我們更快的完成選擇的過程。
public class Twitter { public Twitter() { users = new HashMap<>(); } public static int timestamp = 0; private Mapusers; /** 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; } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/73577.html
摘要:的想法就是用每次得到最小的鏈表頭的值,輸出。每個都有一個關注人列表,用儲存。用戶可以發消息,關注別人,取消關注別人。可以系統得到關注人的消息合集,這個方法必須在這個層級。因為用戶只知道自己的信息。 Merge k Sorted Lists /** * Definition for singly-linked list. * public class ListNode { * ...
摘要:首先建立按時間戳從大到小排列的,找到中的,出其中在中存在的,把每一個的推特鏈表放入,再從中取頭十條推特的放入結果數組。 Design Twitter Note 建立兩個HashMap,一個存user,一個存tweets。以及整型的時間戳timestamp。user的k-v pair是userId-follower_set,tweets的k-v pair是userId-tweets_li...
摘要:返回的是表示是否走到了結尾。起到的就是緩存作用,因為調用之后馬上就走到下一個了。如果調用,返回用得到和最初的輸入相同的做相同的步驟存入不斷拆開得到結果。思想就是來自括號,后面也會跟進的專題 Iterator其實就是一個單鏈表,無法回頭看。java里很多數據結構都有這個接口,使用時需要initalize,得到一個iterator. 調用next()返回的是一個object, 指向的是下一...
摘要:題目鏈接題目分析設計一個哈希類。需要有添加元素函數,判斷元素存在的函數,移除元素函數。思路這真的沒什么好說的了我把要存的值作為數組的鍵存儲。最終代碼若覺得本文章對你有用,歡迎用愛發電資助。 D87 705. Design HashSet 題目鏈接 705. Design HashSet 題目分析 設計一個哈希類。 需要有add添加元素函數,contains判斷元素存在的函數,remov...
摘要:題目鏈接題目分析自行設計一個。需要實現題目內指定的函數。思路我覺得這個沒什么好說的吧最終代碼若覺得本文章對你有用,歡迎用愛發電資助。 D75 706. Design HashMap 題目鏈接 706. Design HashMap 題目分析 自行設計一個hashmap。 需要實現題目內指定的函數。 思路 我覺得這個沒什么好說的吧… 最終代碼
閱讀 2505·2023-04-25 19:31
閱讀 2239·2021-11-04 16:11
閱讀 2805·2021-10-08 10:05
閱讀 1515·2021-09-30 09:48
閱讀 2315·2019-08-30 15:56
閱讀 2406·2019-08-30 15:56
閱讀 2174·2019-08-30 15:53
閱讀 2268·2019-08-30 15:44