产品工艺设计_工程咨询资信资质办理_今天的新闻内容_seo服务合同

【题目】：146. LRU 缓存

LRU：最近最少未使用，很少被请求的数据才会被淘汰掉

本质：让不经常访问的数据往下排，经常访问的数据往上排。

这样会导致：冷门数据在最下边，热门数据在最上边。
如果访问的数据缓存中没有且缓存已经满了：把最下边的数据淘汰掉，再把刚访问的数据放到上边（换页）

分析：

1. 选用什么数据结构？
   数组：添加一个节点，所有节点都要往后移动，时间复杂度O(n)
   链表：添加节点、删除节点只需要改变节点指向，时间复杂度O(1)。只需要改变指针的指向即可。由于不仅要直到节点的下一位，还需要直到节点的上一位，所以使用双向链表。
2. 怎么找到链表的某个节点？
   正常查询链表的某个节点，需要逐个遍历链表元素，时间复杂度O(n)。那有没有办法优化到O(1)的时间复杂度呢？

hashMap的查询时间复杂度是O(1)，可以用hashMap来存储链表节点。

最后选择数据结构如下：

1. 双向链表数据结构

class Node {
public:    int key;int value;Node *pre;Node *next;Node(int key, int value) {this->key = key;this->value = value;this->pre = nullptr;this->next = nullptr;}Node() {this->key = 0;this->value = 0;this->pre = nullptr;this->next = nullptr;}
};

class LRUCache {
public:int capacity;int size;Node *head; // 头节点（哨兵）Node *tail; // 尾节点（哨兵）unordered_map<int, Node*> mp; // mapLRUCache(int capacity) {this->capacity = capacity;this->size = 0;// 初始化双向链表head = new Node();tail = new Node();head->next = tail;tail->pre = head;}int get(int key) {if(mp.find(key) == mp.end()) { // 未找到return -1;}Node *node = mp[key];deleteNodeAndInsertHead(node);return node->value;}void put(int key, int value) {if(mp.find(key) == mp.end()) { // 缓存中没有if(size == capacity) { // 缓存已满，调页Node *delNode = tail->pre; // 要调出的节点deleteNode(delNode); // 调出mp.erase(delNode->key);// 更新map}else {// 缓存未满 - 直接提到头部++size; //更新size}Node *node = new Node(key, value);insertHead(node); // 提到头部mp[key] = node; // 更新map}else {// 缓存中有 - 更新 - 提到头部Node *node = mp[key];node->value = value; // 更新nodemp[key] = node; // 更新mapdeleteNodeAndInsertHead(node); // 提到头部}}
private:// 删除节点void deleteNode(Node *node) {node->pre->next = node->next;node->next->pre = node->pre;}// 插入头部void insertHead(Node *node) {head->next->pre = node;node->next = head->next;node->pre = head;head->next = node;}// 删除节点插入头部的连续操作(正常访问一个节点，都需要做这两步操作)void deleteNodeAndInsertHead(Node *node) {deleteNode(node);insertHead(node);}
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)