146-LRU 缓存（力扣题解）

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

输入输出

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

代码

c++版

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr){};    // 构造函数
    DLinkedNode(int k, int v): key(k), value(v), prev(nullptr), next(nullptr){};

};

class LRUCache {

private: 
    unordered_map<int, DLinkedNode*> mp;  // 哈希表
    DLinkedNode *head, *tail;   // 头尾节点
    int size, capacity;        // 链表长度，链表最大容量

public:
    LRUCache(int capacity) {
        size = 0;
        this->capacity = capacity;
        head = new DLinkedNode();   // 创建头尾节点
        tail = new DLinkedNode();
        head->next = tail; 
        tail->prev = head;
    }
    
    int get(int key) {
        // 若不存在返回-1
        if(mp.count(key) == 0) return -1;

        // 若存在返回值, 并且移动到链表头部
        DLinkedNode *node = mp[key];
        moveToHead(node);   // 移动到链表头
        
        return node->value;
    }
    
    void put(int key, int value) {
        // 如果存在，修改值并且移动到链表头
        if (mp.count(key) == 1) {
            mp[key]->value = value;
            moveToHead(mp[key]);
        }else{          // 不存在，检查容量，容量满足不删除，容量不满足删除
            // 创建节点
            DLinkedNode *node = new DLinkedNode(key, value); 
            mp[key] = node; // 加入mp
            addHead(node); 
            size ++;
            if(size > capacity) {
                size--;
                moveTail(); 
            }
        }
    
    }

    // 移动到头结点
    void moveToHead(DLinkedNode *node){
        moveNode(node);
        addHead(node);
    }
    void moveNode(DLinkedNode *node){
        node->prev->next = node->next; // x->y->z变为x->z
        node->next->prev = node->prev; // x<-y<-z变为x<-z
    }
    // 添加节点到头结点
    void addHead(DLinkedNode *node){
        node->next = head->next;
        node->next->prev = node;
        node->prev = head;
        head->next = node;
    }
    // 删除尾节点
    void moveTail(){
        DLinkedNode *node = tail->prev; // 尾节点
        mp.erase(node->key);
        moveNode(node);
        delete node;
    }
};

/**
 * 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);
 */

go语言版

type DLinkedNode struct{
    key, value int
    prev, next *DLinkedNode
}

type LRUCache struct {
    size, capacity int
    head, tail *DLinkedNode
    mp map[int]*DLinkedNode
}

func initDL(key int, value int) *DLinkedNode{
    return &DLinkedNode{
        key: key,
        value: value,
    }
}

func Constructor(capacity int) LRUCache {
    l := LRUCache{
        size: 0,
        capacity: capacity,
        head: initDL(0, 0),
        tail: initDL(0, 0),
        mp: map[int]*DLinkedNode{},
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}


func (this *LRUCache) Get(key int) int {

    // 不存在
    if _, k := this.mp[key]; !k{
        return -1
    }  
    // 存在
    node := this.mp[key]
    this.moveToHead(node)
    return node.value
}


func (this *LRUCache) Put(key int, value int)  {
    if _, k := this.mp[key]; k {    // 存在
        node := this.mp[key]
        node.value = value
        this.moveToHead(node)
    }else{                          // 不存在
        node := initDL(key, value)
        this.mp[key] = node
        this.addHead(node)
        this.size++
        if this.size > this.capacity {
            this.moveTail()
            this.size--
        }
    }
}

 // 移动到头结点
func (this *LRUCache)  moveToHead(node *DLinkedNode){
    this.moveNode(node);
    this.addHead(node);
}
func (this *LRUCache)  moveNode(node *DLinkedNode){
    node.prev.next = node.next; // x->y->z变为x->z
    node.next.prev = node.prev; // x<-y<-z变为x<-z
}
// 添加节点到头结点
func (this *LRUCache)  addHead(node *DLinkedNode){
    node.next = this.head.next;
    node.next.prev = node;
    node.prev = this.head;
    this.head.next = node;
}
// 删除尾节点
func (this *LRUCache)  moveTail(){
    node := this.tail.prev; // 尾节点
    delete(this.mp, node.key)
    this.moveNode(node);
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */