两道数据结构设计题
- 146 LRU Cache
要求：设计一个最少被访问的cache
思路：使用unordered_map作为cache({key, {value, iter of key}})，可以在get的时候保证O(1)的复杂度。使用list存储key可以在保证满足最少被访问的同时保证O(1)的复杂度。
class LRUCache {
private:
int cap;
list<int> used;
unordered_map<int, pair<int, list<int>::iterator>> cache;//<key,<value,iter of key>>
void touch(unordered_map<int, pair<int, list<int>::iterator>>::iterator it){
int key = it->first;
used.erase(it->second.second);
used.push_front(key);
it->second.second = used.begin();
}
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
auto it = cache.find(key);
if(it == cache.end()) return -1;
touch(it);
return it->second.first;
}
void put(int key, int value) {
auto it = cache.find(key);
if(it != cache.end()){
touch(it);
}else{
if(cache.size() == cap){
cache.erase(used.back());
used.pop_back();
}
used.push_front(key);
}
cache[key] = {value, used.begin()};
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
- 355 Design Twitter
题意：设计题，设计一个twitter
思路：首先定义Tweet的数据结构以及盛放tweet和follower的容器：
struct Tweet{
int id;
int time;
Tweet(int id, int time) : id(id), time(time){}
};
int time;
unordered_map<int, vector<Tweet>> tweets;//{userId,[tweetId]}
unordered_map<int, unordered_set<int>> following;//{userid, [followees]}
使用优先队列来实现最为困难的vector<int> getNewsFeed(int userId)函数：
struct mycompare{
bool operator()(Tweet& p1, Tweet& p2){
return p1.time < p2.time;
}
};
priority_queue<Tweet,vector<Tweet>, mycompare> pq;
完整的程序如下：
class Twitter {
struct Tweet{
int id;
int time;
Tweet(int id, int time) : id(id), time(time){}
};
int time;
unordered_map<int, vector<Tweet>> tweets;//{userId,[tweetId]}
unordered_map<int, unordered_set<int>> following;//{userid, [followees]}
struct mycompare{
bool operator()(Tweet& p1, Tweet& p2){
return p1.time < p2.time;
}
};
public:
/** Initialize your data structure here. */
Twitter(){time = 0;}
/** Compose a new tweet. */
void postTweet(int userId, int tweetId) {
tweets[userId].push_back(Tweet(tweetId, time++));
}
/** 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> ret;
priority_queue<Tweet,vector<Tweet>, mycompare> pq;
for(auto& u: following[userId]){
auto& t = tweets[u];
if(t.size() > 0)
for(auto a : t) pq.push(a);
}
auto& t = tweets[userId];
if(t.size() > 0)
for(auto a : t) pq.push(a);
int index = 0;
while(index < 10 && !pq.empty()){
auto tmp = pq.top();
pq.pop();
ret.push_back(tmp.id);
index ++;
}
return ret;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
void follow(int followerId, int followeeId) {
if(followerId != followeeId)
following[followerId].insert(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
void unfollow(int followerId, int followeeId) {
following[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);
*/
