146. LRU Cache

题目

设计一个数据结构，来实现 LRU 缓存算法
LRU 缓存算法的特点是

1. 有一个初始化的固定容量
2. get 函数返回 value 值，如果不存在返回 -1
3. put 函数更新 k，v 值。如果超过最大缓存，则驱逐一个最长时间未使用的元素。

题目要求 get 和 put 函数都要在 O(1) 时间复杂度完成。

解析

如果要在 O(1) 时间复杂度里进行 get，需要一个 map 结构。
如果 put 时需要驱逐，则需要一个指针始终指向需要驱逐的元素。
为了始终能够指向需要驱逐的元素，需要在每次 get 时将使用过的元素置于最顶端，这样末尾的元素就是需要排除的元素。所以链表是一个好选择，而且需要双向链表，这样能够定位上下指针以便于移动后拼接该链表。

所以整体的方案是，map 的 value 指向双向链表节点，链表节点存储值。

伪代码

代码

type Node struct {
    Key int
    Val int
    Pre *Node
    Next *Node
}

type LRUCache struct {
    Cache map[int]*Node
    Vhead *Node
    Vtail *Node
    Cur int
    Cap int
}

func Constructor(capacity int) LRUCache {
    vh := &Node{}
    vt := &Node{}
    vh.Next = vt
    vt.Pre = vh
    return LRUCache{
        Cache: make(map[int]*Node),
        Vhead: vh,
        Vtail: vt,
        Cur: 0,
        Cap: capacity,
    }
}

func (this *LRUCache) Get(key int) int {
    node, ok := this.Cache[key]
    if !ok {
        return -1
    }
    
    // set node to first
    node.Pre.Next = node.Next
    node.Next.Pre = node.Pre
    
    node.Next = this.Vhead.Next
    node.Pre = this.Vhead
    
    this.Vhead.Next.Pre = node
    this.Vhead.Next = node
    
    return node.Val
}

func (this *LRUCache) Put(key int, value int)  {
    node, ok := this.Cache[key]
    if ok {
        node.Val = value
        node.Pre.Next = node.Next
        node.Next.Pre = node.Pre
    } else {
        if this.Cur >= this.Cap {
            delete(this.Cache, this.Vtail.Pre.Key)
            this.Vtail.Pre.Pre.Next = this.Vtail
            this.Vtail.Pre = this.Vtail.Pre.Pre
        } else {
            this.Cur++
        }
        node = &Node{Key: key, Val: value}
        this.Cache[key] = node
    }
    
    node.Next = this.Vhead.Next
    node.Pre = this.Vhead
    
    this.Vhead.Next.Pre = node
    this.Vhead.Next = node
}

image.png