题目要求 get 和 set 请求都是 O(1)O(1)O(1) 的平均时间复杂度，那很容易想到使用 map，但如果 value 是 int 型，那就很难实现 LRU 的目的，我们可以设计一个双端链表，将最近访问和插入的节点插入到链表的头节点，当缓存不够时，只需要移出链表尾部的节点，因为要是 set 操作时间复杂度也是 O(1)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); */