❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/lru-cache/description/

❞

题目

请你设计并实现一个满足 「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 必须以 的平均时间复杂度运行。

示例：

// 定义双向链表
type MyListNode struct {
    key, value int
    pre, next *MyListNode
}

type LRUCache struct { 
    size, capacity int
    cache map[int]*MyListNode
    protectHead, protectTail *MyListNode
}


func Constructor(capacity int) LRUCache {
    lruCache := LRUCache{
        size: 0,
        capacity: capacity,
        cache: map[int]*MyListNode{},
        protectHead: &MyListNode{},
        protectTail: &MyListNode{},
    }

    lruCache.protectHead.next = lruCache.protectTail
    lruCache.protectTail.pre = lruCache.protectHead
    return lruCache
}


func (this *LRUCache) Get(key int) int {
    if listNode, ok := this.cache[key]; ok {
        this.moveToTail(listNode);
        return listNode.value;
    }else{
        return -1
    }
}


func (this *LRUCache) Put(key int, value int)  {
    if listNode, ok := this.cache[key]; ok {
        listNode.value = value;
        this.moveToTail(listNode);
        return;
    }
    if(this.size == this.capacity){
        headNode := this.protectHead.next;
        this.remove(headNode);
        delete(this.cache, headNode.key);
        this.size--
    }

    listNode := &MyListNode{
        key: key,
        value: value,
    }


    this.addToTail(listNode)
    this.cache[key] = listNode
    this.size++
}

// 删除指定节点
func (this *LRUCache) remove(listNode *MyListNode){
    listNode.pre.next = listNode.next;
    listNode.next.pre = listNode.pre;

    listNode.pre = nil;
    listNode.next = nil;
}


// 添加到末尾
func (this *LRUCache) addToTail(listNode *MyListNode){
    this.protectTail.pre.next = listNode
    listNode.pre = this.protectTail.pre

    listNode.next = this.protectTail
    this.protectTail.pre = listNode
}


// 从当前位置移动到末尾
func (this *LRUCache) moveToTail(listNode *MyListNode){
    this.remove(listNode);
    this.addToTail(listNode);
}

复杂度分析

• 时间复杂度：，get 和 put 时间复杂度均为 。
• 空间复杂度：，n 为给定的容量 capacity，哈希表存放 n 对值，双向链表存放 n + 2个节点，忽略常量后空间复杂度为。

点个在看你最好看

CLICK TO SEE YOU LOOK THE BEST