題目要求 get 和 set 請求都是 $O(1)O(1)$ 的平均時間復(fù)雜度，那很容易想到使用 map，但如果 value 是 int 型，那就很難實現(xiàn) LRU 的目的，我們可以設(shè)計一個雙端鏈表，將最近訪問和插入的節(jié)點插入到鏈表的頭節(jié)點，當(dāng)緩存不夠時，只需要移出鏈表尾部的節(jié)點，因為要是 set 操作時間復(fù)雜度也是 $O(1)O(1)$ 所以必須時刻記錄尾節(jié)點的位置，這也是為什么要使用雙端鏈表的目的。

// 雙向鏈表
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
}

// 生成鏈表節(jié)點
func InitialDLinkNode(key,value int) *DLinkedNode{
    return &DLinkedNode{key:key,value:value}
} 


func Constructor(capacity int) Solution {
    solution:= Solution{
        Capacity:capacity,
        // 生成虛擬頭節(jié)點
        head:InitialDLinkNode(0,0),

        // 生成虛擬尾節(jié)點
        tail:InitialDLinkNode(0,0),

        Cache:make(map[int]*DLinkedNode,capacity),
    }
    // 初始化head和tail節(jié)點
    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{

        // 最近訪問的節(jié)點移動到鏈表頭節(jié)點
        this.moveToHead(node)
        return node.value
    }
    
}


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

        // 根據(jù)key，value生成鏈表節(jié)點
        newNode:=InitialDLinkNode(key,value)
        this.Cache[key]=newNode

        // 新節(jié)點插入到鏈表頭
        this.addToHead(newNode)
        this.size++

        // 緩存滿
        if this.size>this.Capacity{
            // 移除尾節(jié)點
            removed:=this.removeTail()
            delete(this.Cache,removed.key)
            this.size--
        }
    }else{
            node.value=value

            // 最近訪問的節(jié)點移動到鏈表頭
            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

}

// 刪除節(jié)點
func (this *Solution) removeNode(node *DLinkedNode){
    node.prev.next=node.next
    node.next.prev=node.prev
}

// 移動節(jié)點到頭節(jié)點位置
func (this *Solution) moveToHead(node *DLinkedNode){
    this.removeNode(node)
    this.addToHead(node)
}

// 移除尾節(jié)點
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);
 */