Design Twitter
應用面向對象設計(OO)模擬Twitter的幾個功能晴音，分別是：
- 發(fā)推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 follow.
- 取關unfollow(followerId, followeeId): Follower unfollows a followee.
跟微博一樣??
首先要考慮的是琳要，這里應該有用戶液斜、推文肃拜，用戶很簡單笤闯，一個整形就可以表示响逢。推文需要有，userId唤崭，tweetId拷恨，timestamp（我們這里并不需要詳細的時間，只要有每條推文的先后順數(shù)就可以了）谢肾，對此我們使用struct tweet
接下來分析功能腕侄，每一個用戶都應該有一個數(shù)組來記錄他的關注對象，另外一個數(shù)組紀錄他的推文芦疏，這里可以選擇建一個structure記錄這些數(shù)據(jù)冕杠，但是在這道題里我們只用到了兩個unordered_maps存放對應數(shù)據(jù)，在map中每個整形（userId）都有對應的followees和tweets
有了這樣的數(shù)據(jù)結構呢酸茴，postTweet, follow, unfollow都很好實現(xiàn)了分预，只需要對map進行相應操作即可。
有些難得是getNewsFeed這個函數(shù)薪捍，返回用戶關注的最近十條推文噪舀，包括他自己的魁淳。對于這種有順序的東西很容易想到priority_queue, 下面這個solution用一個priority-queue存儲該用戶關注的每個用戶的推文的begin iterator, end iterator. begin iterator用于從每個follow發(fā)的最新的推文中選出最新的。
class Twitter {
private:
struct tweet {
int userId;
int tweetId;
int timesStamp;
tweet(int x, int y, int z): userId(x), tweetId(y), timesStamp(z){};
};
struct mycompare {
bool operator()(pair<list<tweet>::iterator, list<tweet>::iterator> p1,
pair<list<tweet>::iterator, list<tweet>::iterator> p2) {
return p1.first->timesStamp < p2.first->timesStamp;
}
};
int timeLabel = 0;
unordered_map<int, unordered_set<int>> followees;
unordered_map<int, list<tweet>> tweets;
public:
/** Initialize your data structure here. */
Twitter() {}
/** Compose a new tweet. */
void postTweet(int userId, int tweetId) {
followees[userId].insert(userId);
tweets[userId].push_front(tweet(userId, tweetId, timeLabel));
timeLabel++;
}
/** 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. */
vector<int> getNewsFeed(int userId) {
vector<int> res;
if (followees.find(userId) == followees.end()) return res;
priority_queue<pair<tweet, tweet>,
vector<pair<tweet, tweet>>,
mycompare> pq;
for (auto it = followees[userId].begin(); it != followees[userId].end(); it++)
if (tweets[*it].begin() != tweets[*it].end())
pq.push(make_pair(* tweets[*it].begin(), * tweets[*it].end()));
int index = 0;
while(!pq.empty() && index < 10) {
auto tmp = pq.top();
pq.pop();
res.push_back(tmp.first.tweetId);
if (++tmp.first != tmp.second)
pq.push(tmp);
index++;
}
return res;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
void follow(int followerId, int followeeId) {
followees[followerId].insert(followerId);
followees[followerId].insert(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
void unfollow(int followerId, int followeeId) {
if (followees.find(followerId) != followees.end() && followerId != followeeId) {
followees[followerId].erase(followeeId);
}
}
};
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* vector<int> param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
*/
