题解 | #go语言设计LRU缓存结构#

题目要求 get 和 set 请求都是 $O(1)O(1)$ 的平均时间复杂度，那很容易想到使用 map，但如果 value 是 int 型，那就很难实现 LRU 的目的，我们可以设计一个双端链表，将最近访问和插入的节点插入到链表的头节点，当缓存不够时，只需要移出链表尾部的节点，因为要是 set 操作时间复杂度也是 $O(1)O(1)$ 所以必须时刻记录尾节点的位置，这也是为什么要使用双端链表的目的。

// 双向链表
type DLinkedNode struct{
    key,value int
    prev,next *DLinkedNode
}
type Solution struct {
     // write code here
     Capacity,size int
     Cache map[int]*DLinkedNode
     head,tail *DLinkedNode
}

// 生成链表节点
func InitialDLinkNode(key,value int) *DLinkedNode{
    return &DLinkedNode{key:key,value:value}
} 


func Constructor(capacity int) Solution {
    solution:= Solution{
        Capacity:capacity,
        // 生成虚拟头节点
        head:InitialDLinkNode(0,0),

        // 生成虚拟尾节点
        tail:InitialDLinkNode(0,0),

        Cache:make(map[int]*DLinkedNode,capacity),
    }
    // 初始化head和tail节点
    solution.head.next=solution.tail
    solution.tail.prev=solution.head
    return solution
}


func (this *Solution) get(key int) int {
    // write code here
    if node,ok:=this.Cache[key];!ok{
        return -1
    }else{

        // 最近访问的节点移动到链表头节点
        this.moveToHead(node)
        return node.value
    }
    
}


func (this *Solution) set(key int, value int)  {
    // write code here
    if node,ok:=this.Cache[key];!ok{

        // 根据key，value生成链表节点
        newNode:=InitialDLinkNode(key,value)
        this.Cache[key]=newNode

        // 新节点插入到链表头
        this.addToHead(newNode)
        this.size++

        // 缓存满
        if this.size>this.Capacity{
            // 移除尾节点
            removed:=this.removeTail()
            delete(this.Cache,removed.key)
            this.size--
        }
    }else{
            node.value=value

            // 最近访问的节点移动到链表头
            this.moveToHead(node)
        }
}

// 插入到链表头
func (this *Solution) addToHead(node *DLinkedNode){
    node.prev=this.head
    node.next=this.head.next
    this.head.next.prev=node
    this.head.next=node

}

// 删除节点
func (this *Solution) removeNode(node *DLinkedNode){
    node.prev.next=node.next
    node.next.prev=node.prev
}

// 移动节点到头节点位置
func (this *Solution) moveToHead(node *DLinkedNode){
    this.removeNode(node)
    this.addToHead(node)
}

// 移除尾节点
func (this *Solution) removeTail()(node *DLinkedNode){
    node=this.tail.prev
    this.removeNode(node)
    return node
}
/**
 * Your Solution object will be instantiated and called as such:
 * solution := Constructor(capacity);
 * output := solution.get(key);
 * solution.set(key,value);
 */