问题
设计和实现最近最少使用(LRU)缓存的数据结构。它应该支持以下操作:获取和设置。
get(key)
-如果键在缓存中,则获取键的值(始终为正),否则返回-1。
set(key, value)
-如果键不存在,请设置或插入值。当缓存达到其容量时,它应在插入新项目之前使最近最少使用的项目无效。
我的程序
class LRUCache {
public:
LRUCache(int capacity) {
LRUCache::capacity = capacity;
len = 0;
}
int get(int key) {
if (table.find(key) != table.end()) {
removeNode(table[key]);
setHead(table[key]);
return table[key]->value;
} else {
return -1;
}
}
void set(int key, int value) {
if(table.find(key) != table.end()) {
ListNode *curr = table[key];
curr->value = value;
removeNode(curr);
setHead(curr);
} else {
ListNode *curr = new ListNode(key, value);
if(len < capacity) {
setHead(curr);
table[key] = curr;
len++;
} else {
ListNode *tmp = tail;
tail = tail->prev;
if(tail) {
tail->next = nullptr;
}
table.erase(tmp->key);
delete tmp;
setHead(curr);
table[key] = curr;
}
}
}
private:
struct ListNode {
int key, value;
ListNode *prev, *next;
ListNode(int key, int value)
: key(key)
, value(value)
, prev(nullptr)
, next(nullptr) {
}
};
unordered_map<int, ListNode*> table;
ListNode *head, *tail;
int capacity;
int len;
void removeNode(ListNode *node) {
if(node->prev) {
node->prev->next = node->next;
} else {
head = node->next;
}
if(node->next) {
node->next->prev = node->prev;
} else {
tail = node->prev;
}
}
void setHead(ListNode *node) {
node->next = head;
node->prev = nullptr;
if(head) {
head->prev = node;
}
head = node;
if(!tail) {
tail = node;
}
}
};
输入样例:
1 // capacity
2 1 // set(int, int)
1 // get(int)
在我的机器上输出:
-1
在线判断编译器中的输出:
运行时错误
到底怎么了?问题是Leetcode。
您无需初始化head
和tail
,因此它们具有不确定的值。如果这些值恰好为空,则程序将按预期运行;否则,程序将按预期运行。如果没有,可能会发生任何事情。
像Valgrind这样的运行时分析工具非常适合发现此类错误。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句