推荐订阅源

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

这个题目考的非常综合。

类似问题考虑要点：

1. get，算是cache hit，首先要查找到这个node，然后再把这个node放到第一位

2. setval, 这个算是更新，如果找到，那么把他移到头上，如果找不到那就新建一个放到第一位。

因为涉及到元素的顺序，元素的更新，那么vector based的方案，统统不行。

最直接的实现是使用 double link list，然后查找就是线性查找，插入，删除O（1）但是当链表比较大时，查找就很慢。

需要查找快，那么就是hash或者map 这里最最合适的就是hash。

所以要搞出一个比较诡异的结构，

把双向链表放到一个以Key为哈希key的hash表中。

那么在查找的时候可以利用hash的O（1），快速的判断key是否在链表中。

当找到key之后，找到对应的链表结点，然后通过O(1)的复杂度，来更新链表。

另外一个trick是链表的操作中，使dumb node ，非常有助于简化问题。

因为是双向队列，所以使用两个dumb node。

class LRUCache{
public:
    struct LinkList
    {
        int val;
        int key;
        LinkList* next;
        LinkList* prev;
        LinkList(int k, int x) : key(k), val(x), next(NULL), prev(NULL){}
    };

    //link list operation to simplify operation introuduce 2 dummy node, head and tail
    LinkList *tail = NULL;
    LinkList *head = NULL;
    int gcapcity = 0;
    int size = 0;

    // due to performance hit, so put the key in the map or hastable, will
    // directly improve the performance of searching, actually,searching directly based on the map/hastable
    //
    unordered_map<int, LinkList*> nodeMap;

    LRUCache(int capacity) {
        gcapcity = capacity;
        tail = new LinkList(-1, -1);
        head = new LinkList(-1, -1);
        head->next = tail;
        tail->prev = head;
        size = 0;

    }

    void PutSingleNodetoHead(LinkList* node)
    {
        if (node == NULL) return;
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    int get(int key)
    {
        int val = -1;
        unordered_map<int, LinkList*>::iterator it = nodeMap.find(key);
        if (it != nodeMap.end()) //found
        {
            LinkList* node = it->second;
            val = node->val;
            node->prev->next = node->next;
            node->next->prev = node->prev;
            PutSingleNodetoHead(node);
        }

        return val;
    }

    void set(int key, int value) {
        unordered_map<int, LinkList*>::iterator it = nodeMap.find(key);
        if (it == nodeMap.end())
        {
            //not exist need insert one
            LinkList *node = new LinkList(key, value);
            PutSingleNodetoHead(node);
            nodeMap[key] = node;
            size++;

            if(size>gcapcity){  
                node = tail->prev;  
                tail->prev = node->prev;  
                node->prev->next = tail;  
                it = nodeMap.find(node->key);  
                nodeMap.erase(it);  
                delete node;  
            } 

        }
        else
        {
            LinkList* ptnode = it->second;
            ptnode->val = value;
            ptnode->prev->next = ptnode->next;
            ptnode->next->prev = ptnode->prev;
            PutSingleNodetoHead(ptnode);

        }

    }
};