#include <iostream> #include <map> using namespace std; class ListNode { public: int val; int key; ListNode* pre; ListNode* next; ListNode(int ky, int va) :key(ky), val(va), pre(nullptr), next(nullptr) {} ListNode() :pre(nullptr), next(nullptr), key(-1), val(-1){} }; class LRU { private: map<int, int> kvMap; ListNode* head; ListNode* end; int size; public: LRU() :head(nullptr),end(nullptr), size(0) {} LRU(int size) :head(nullptr), end(nullptr), size(size) {} int get(int key) { if (kvMap.find(key) == kvMap.end()) { return -1; } ListNode* p = head; ListNode* pre = nullptr; while (p) { if (p->key == key) { if (p == head && p->next) { head = p->next; } else if ((p == head && !p->next )||(p == end)) { return kvMap[key]; } if (pre) { pre->next = p->next; } if (p->next) { p->next->pre = pre; } p->pre = end; end->next = p; p->next = nullptr; end = p; } pre = p; p = p->next; } return kvMap[key]; } void put(int key, int val) { if (size == 0) { return; } if (kvMap.find(key) != kvMap.end()) { kvMap[key] = val; ListNode* p = head; while (p) { if (p->key == key) { p->val = val; return; } p = p->next; } return; } if (kvMap.size() + 1 > size) { ListNode* old = head; kvMap.erase(old->key); head = head->next; if (end == old) { end = nullptr; } delete old; } kvMap[key] = val; if (head == nullptr) { head = new ListNode(key, val); } else if (end == nullptr) { end = new ListNode(key, val); head->next = end; end->pre = head; } else { end->next = new ListNode(key, val); end->next->pre = end; end = end->next; } } }; int main() { int size; cin >> size; LRU lru(size); char x; int k, v; while (cin >> x) { if (x == 'p') { cin >> k >> v; lru.put(k, v); } else { cin >> k; cout << lru.get(k) << endl; } } } // 64 位输出请用 printf("%lld")
写的不是很好,主要就是一个双向链表的更新,好像hash表也是不必要的