突击刷题： LRU Cache

LintCode上有这个题，不多说了，把glassdoor上的写一遍再说吧。。。后面有空再慢慢更新lintCode的答案。。。


为什么服务器初始化的时候要用LRU Cache?

所有操作都为O(1)复杂度

坏处？
The fundamental locality principle claims that if a process visits a location in the memory, it will probably revisit the location and its neighborhood soon. The advanced locality principle claims that the probability of revisiting will increased if the number of the visits is bigger. LRU supports just the fundamental locality principle. What will happen if a process scans a huge database?


拓展题目就是LFU， 最常用的， 实现的话用heap...基本一样，维护一个最小堆

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

#include <list> class LRUCache{ public: struct Node{ int key; int value; Node(int k, int v) :key(k),value(v){ }; }; // @param capacity, an integer LRUCache(int capacity) { // write your code here myCapacity=capacity; } // @return an integer int get(int key) { // write your code here if (myMap.find(key)==myMap.end()){ return -1; } int v=(*myMap[key])->value; move2Front(key); return v; } // @param key, an integer // @param value, an integer // @return nothing void set(int key, int value) { // write your code here if (myMap.find(key)==myMap.end()){ Node* node = new Node(key, value); myList.push_front(node); myMap[key]=myList.begin(); if (myMap.size()>myCapacity){ Node* node= myList.back(); myMap.erase(node->key); delete node; myList.pop_back(); } return; } (*myMap[key])->value=value; move2Front(key); } private: void move2Front(int key){ if (myMap.find(key)==myMap.end()) return; Node* node = *myMap[key]; myList.remove(*myMap[key]); myList.push_front(node); myMap[key]=myList.begin(); }; int myCapacity; list<Node*> myList; unordered_map<int, list<Node*>::iterator> myMap; };