LeetCode 146. LRU 缓存机制（双向链表+hash）

题意：

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；
如果关键字不存在，则插入该组「关键字-值」。
当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
 

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

数据范围:
1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 1e4
最多调用 3 * 1e4 次 get 和 put

解法：

最近最少使用算法需要将最常用的(key,value)放在最前面,
需要数据结构满足删除和插入操作,可以用链表做,
对于删除拼接的操作,需要双向链表才能实现.

为了实现O(1)查询节点位置,需要对节点hash一下,这里用unordered_map实现.

其他地方就是简单模拟了.

code：

struct Node{
    int key;
    int val;
    Node* pre;
    Node* nt;
    Node(int x,int y){
        key=x,val=y,pre=nt=NULL;
    }
    Node(int x,int y,Node* p,Node* q){
        key=x,val=y,pre=p,nt=q;
    }
};
class LRUCache {
public:
    unordered_map<int,Node*>mp;
    Node* head,*tail;
    int sz;
    int cap;
    void tohead(Node* p){//将p结点移动到头部.
        Node* h=head->nt;
        head->nt=p;
        p->nt=h;
        p->pre=head;
        h->pre=p;
    }
    void out(Node* p){//将p移出原来的位置.
        Node* pp=p->pre;
        Node* ntt=p->nt;
        pp->nt=ntt;
        ntt->pre=pp;
    }
    LRUCache(int capacity) {
        head=new Node(0,0);//虚头
        tail=new Node(0,0);//虚尾
        head->nt=tail;
        tail->pre=head;
        mp.clear();
        cap=capacity;
        sz=0;
    }
    int get(int key) {
        if(mp.count(key)){
            Node* p=mp[key];
            out(p);
            tohead(p);
            return p->val;
        }else{
            return -1;
        }
    }
    void put(int key, int value) {
        if(mp.count(key)){
            Node* p=mp[key];
            p->val=value;
            out(p);
            tohead(p);
        }else{
            Node* p=new Node(key,value);
            mp[key]=p;
            tohead(p);
            sz++;
            if(sz>cap){//满了,删掉尾部
                Node* t=tail->pre;
                mp.erase(t->key);
                out(t);
                sz--;
            }
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

最后

以上就是香蕉衬衫为你收集整理的LeetCode 146. LRU 缓存机制（双向链表+hash）的全部内容，希望文章能够帮你解决LeetCode 146. LRU 缓存机制（双向链表+hash）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。