数据结构设计题
LC146.LRU缓存
手写双向链表，前后两个哨兵节点，使用哈希表快速查询
class LRUCache {
//容量大小
int cap = 0;
//双向链表
struct Node {
int key = 0;
int val;
Node* prev = nullptr;
Node* next = nullptr;
Node(){};
Node(int _key, int _val):key(_key), val(_val) {}
};
//链表的头尾作为空节点不存储值
Node* head = nullptr, *tail = nullptr;
//key与对应的链表值
unordered_map<int, Node*> umap;
//连接两个链表
void linkTwoNode(Node* preNode, Node* laterNode) {
preNode->next = laterNode;
laterNode->prev = preNode;
}
public:
LRUCache(int capacity) {
//初始化，创建两个新的头尾节点相连，赋值容量
tail = new Node();
head = new Node();
linkTwoNode(head, tail);
cap = capacity;
}
int get(int key) {
if (umap.count(key)) {
//如果存在就将新的value覆盖掉之前的
put(key, umap[key]->val);
return umap[key]->val;
}
return -1;
}
void put(int key, int value) {
Node* newNode = nullptr;
if (umap.count(key)) {
//如果存在就将新的value覆盖掉之前的
umap[key]->val = value;
newNode = umap[key];
//存在当前键值key所表示的数据，需要将其表示的来链表节点提前至头部节点后
//连接当前节点的前后两个节点
linkTwoNode(newNode->prev, newNode->next);
} else {
//没有找到就创建新的节点并加入哈希表
newNode = new Node(key, value);
umap[key] = newNode;
//容量超出预设，清除map的记录，且需要将尾部节点的前一个节点删掉
if (umap.size() > cap) {
umap.erase(tail->prev->key);
linkTwoNode(tail->prev->prev, tail);
}
}
//将需要调整的节点（新节点或者是读取的旧节点）提前到头节点尾部
linkTwoNode(newNode, head->next);
linkTwoNode(head, newNode);
}
};
//使用STL双向链表
class LRUCache {
//存入list迭代器便于快速搜索
unordered_map<int, list<pair<int, int>>::iterator> umap;
//链表存储信息的key和value
list<pair<int, int>> cache;
int size;
public:
LRUCache(int capacity) {
size = capacity;
}
int get(int key) {
if (umap.count(key)) {
//如果有缓存就更新该缓存的位置
//在cache中迭代器umap[key]的位置剪切到cache.begin()
cache.splice(cache.begin(), cache, umap[key]);
return umap[key]->second;
}
return -1;
}
void put(int key, int value) {
if (umap.count(key)) {
//如果有就更新该key的值以及在链表中的位置
umap[key]->second = value;
cache.splice(cache.begin(), cache, umap[key]);
} else {
//没有缓存就要在链表头加入该键值对，并让哈希表指向该节点
cache.insert(cache.begin(), make_pair(key, value));
umap[key] = cache.begin();
//如果超出的容量范围就要删掉链表的尾部并去掉对应的哈希位置
if (cache.size() > size) {
umap.erase(cache.back().first);
cache.pop_back();
}
}
}
};
使用STL，哈希表中存储双向链表的迭代器，每次将最近使用的缓存存入到双向链表的头部
class Solution {
public:
/**
op
*/
vector<int> LRU(vector<vector<int> >& op, int k) {
list<pair<int, int>> cache;
unordered_map<int, list<pair<int, int>>::iterator> umap;
vector<int> res;
for (auto &vec : op) {
//3个数表示要更新或者查询缓存
if (vec.size() == 3) {
//存在这个数表明要更新这个数
if (umap.count(vec[1])) {
//放到前面
cache.splice(cache.begin(), cache, umap[vec[1]]);
//重新赋值键值对
umap[vec[1]]->second = vec[2];
} else {
//不存在这个键就在链表头部插入这个键值对
cache.insert(cache.begin(), make_pair(vec[1], vec[2]));
//添加哈希映射
umap[vec[1]] = cache.begin();
//插入操作可能会超出缓存
if (cache.size() > k) {
umap.erase(cache.back().first);
cache.pop_back();
}
}
} else {
//两个数表示要查询缓存，查询之后还要更新顺序
if (umap.count(vec[1])) {
cache.splice(cache.begin(), cache, umap[vec[1]]);
res.push_back(umap[vec[1]]->second);
}
else res.push_back(-1);
}
}
return res;
}
};
LC380.O(1)时间插入删除获取随机元素
巧妙的使用一个数组及其下标进行随机数查找
class RandomizedSet {
unordered_map<int, int> umap;
vector<int> vec;
public:
RandomizedSet() {
}
bool insert(int val) {
if (umap.count(val)) return false;
//哈希值设置成数组大小，也即该值在数组中的下标
umap[val] = vec.size();
vec.emplace_back(val);
return true;
}
bool remove(int val) {
if (!umap.count(val)) return false;
//通过哈希表先找到这个值的下标
int idx = umap[val];
//这个下标改换成最后一个数，并将对应的哈希值更改
vec[idx] = vec.back();
umap[vec.back()] = idx;
umap.erase(val);
vec.pop_back();
return true;
}
int getRandom() {
return vec[rand() % vec.size()];
}
};
LC716.最大栈
设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。push压栈，pop返回并移除栈顶元素，top返回栈顶元素，peekMax返回栈中最大元素，popMax返回并删除栈中最大元素。
class MaxStack {
//平衡树中的每一个节点存储一个键值对，其中“键”表示某个在栈中出现的值，“值”为一个列表
map<int, vector<list<int>::iterator>> mp;
list<int> stk;
public:
MaxStack() {
}
void push(int x) {
stk.push_front(x);
mp[x].emplace_back(stk.begin());
}
int pop() {
int key = stk.front();
mp[key].pop_back();
if (mp[key].empty()) mp.erase(key);
stk.pop_front();
return key;
}
int top() {
return stk.front();
}
int peekMax() {
return mp.rbegin()->first;
}
int popMax() {
//取出栈顶
int key = mp.rbegin()->first;
//栈顶对应的数组的最后一个迭代器
auto it = mp[key].back();
//将该数组删除掉最后一个链表节点
mp[key].pop_back();
//如果已经空了就删掉
if (mp[key].empty()) mp.erase(key);
//删掉对应的迭代器
stk.erase(it);
return key;
}
};
海康威视工作强度 84人发布