题目分析

LRU缓存是一种常见的内存页面置换算法，其思想是：如果内存已满，并且需要新的数据，那么就需要从内存中将已有的数据和新的数据进行置换，置换的原则是将哪一个最近没有使用，就将哪一个替换出去。小伙伴们了解原理之后，能否实现这个算法呢？

链表+哈希表

要根据键key查找值value，因此我们需要一个哈希映射，因为我们有容量，有时间顺序，因此我们需要一个顺序容器。顺序容器有很多，有vector，deque，list，我们选择哪一个最合适呢？

首先我们比较这三个的区别
**vector：动态数组，元素连续存放。随机访问，或者在尾部插入和删除都是O(1)的时间复杂度，而普通的插入和删除需要移动元素，时间复杂度是O(n)**。

list：双向链表，内存空间是不连续的。在任何地方插入和删除都是O(1)的时间复杂度，但是随机访问的时间复杂度是O(n)的，且必须一个一个进行对比，无法直接索引。

**deque：双端队列，介于vector和list之间，内存分块，每一个存储块之间是连续存放的。允许头部操作和尾部操作。随机访问，头部操作和尾部操作都是O(1)的时间复杂度，而普通的插入和删除时间复杂度是O(n)**。

这里需要大量的移动操作，如果最近使用了内存中的数据，则需要将该数据放入尾部，说明最近已经使用，因此需要频繁的用到删除和插入操作。插入操作都是在尾部插入，vector，deque和list都可以，但是删除操作会在数据中间使用，因此使用list效率更高。

但是问题是我们需要找到该元素，才能将其删除，找到该元素的操作是O(n)的，那应该如何优化呢？

我们可以在哈希表中不仅仅存放键对应的值，而是将键的迭代器指针也存放进哈希表中，这样在查询时，不仅一次能够查到值，而且也能将该迭代器指针查到，这样可以直接操作这个指针。

然后我们分别分析下面这两个步骤的具体实现过程。
put：put操作是向内存中放入元素，如果内存中已经有该元素，那么从哈希映射中查到该元素的指针，从list中移除该指针，并且在尾部重新添加键。修改哈希映射中的值和新的指针。如果内存中没有该元素，则需要分情况讨论，如果内存已满，需要将头部元素剔除，并且将对应的哈希表的键也剔除，因为头部元素是最久没有使用到的数据。然后再在尾部重新添加键，修改哈希映射中的值和新的指针。

get：get操作相对于put操作简单一些，如果哈希表中没有查到，则返回-1，如果哈希表中查到了，说明本次使用到了该数据，需要将这个数据从原来的位置删除，并且添加到尾部。这个过程类似于放入已存在的元素。从哈希映射中查到该元素的指针，从list中移除该指针，并且在尾部重新添加键，修改哈希映射中的指针，并且返回值是哈希映射中的值。

算法的**时间复杂度为$O(1)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<list>
#include<unordered_map>

using namespace std;

class LRUCache {
private:
    int capacity;
    list<int> lis;
    unordered_map<int, pair<int, list<int>::iterator>> dic;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (!dic.count(key)) { return -1; }
        list<int>::iterator it = dic[key].second;
        lis.erase(it);
        lis.push_back(key);
        dic[key].second = --lis.end();
        return dic[key].first;
    }

    void put(int key, int value) {
        if (!dic.count(key)) {
            if (lis.size() == capacity) {
                dic.erase(lis.front());
                lis.pop_front();
            }
        }
        else {
            list<int>::iterator it = dic[key].second;
            lis.erase(it);
        }
        lis.push_back(key);
        dic[key] = { value, --lis.end() };
    }
};

自定义双向链表

这个方法是小伙伴们务必掌握的，这非常锻炼小伙伴们对于数据结构的知识。

我们手动创建一个双向链表，和上面一样，实现在尾部插入和任意节点删除即可，思路和上面完全相同，直接看代码吧。

算法的**时间复杂度为$O(1)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<unordered_map>

using namespace std;

class Node {
public:
    int key, value;
    Node* prev, * next;

    Node() : key(0), value(0), prev(NULL), next(NULL) {}

    Node(int key, int value) : key(key), value(value), prev(NULL), next(NULL) {}
};

class LRUCache {
private:
    unordered_map<int, Node*> dic;
    Node* head, * tail;
    int capacity;

public:
    LRUCache(int capacity) : capacity(capacity) {
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (!dic.count(key)) { return -1; }
        Node* node = dic[key];
        remove(node);
        addToTail(node);
        return node->value;
    }

    void put(int key, int value) {
        if (!dic.count(key)) {
            if (capacity == dic.size()) {
                dic.erase(head->next->key);
                delete remove(head->next);
            }
            Node* node = new Node(key, value);
            addToTail(node);
            dic[key] = node;
        }
        else {
            Node* node = dic[key];
            remove(node);
            addToTail(node);
            dic[key]->value = value;
        }
    }

    void addToTail(Node* node) {
        node->next = tail;
        node->prev = tail->prev;
        tail->prev->next = node;
        tail->prev = node;
    }

    Node* remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        return node;
    }
};

刷题总结

构建类的题型一般都是考察在已有的数据结构上加以变化，形成一种针对于特定问题的数据结构。这要求小伙伴们对数据结构的熟练程度非常高，虽然在笔试中很少遇到这样的题目，但是在面试中可能会让小伙伴们实现某种特定的结果，如字节跳过就曾考察过构造类的问题。可能一道题就会让你与某个岗位失之交臂，或者待遇相差很大，因此小伙伴们要重视起来。