题解 | #设计LRU缓存结构#

//妈妈，我出息了
type Node struct {
    key, value int 
    pre, next *Node
}
func initNode(key, value int) *Node {
    return &Node {
        key : key,
        value : value,
    }
}
type DoubleLinkedList struct {
    head, tail *Node
    size int
}
func initDoubleLinkedList() *DoubleLinkedList {
    dll := &DoubleLinkedList {
        head : initNode(0, 0),
        tail : initNode(0, 0),
        size : 0,
    }
    dll.head.next = dll.tail
    dll.tail.pre = dll.head
    return dll
}
func (this *DoubleLinkedList) addLast(x *Node) {
    x.pre = this.tail.pre
    x.next = this.tail
    this.tail.pre.next = x
    this.tail.pre = x
    this.size++
}
func (this *DoubleLinkedList) remove (x *Node) {
    x.pre.next = x.next
    x.next.pre = x.pre
    x.pre = nil
    x.next = nil
    this.size--
}
func (this *DoubleLinkedList) removeFirst() *Node {
    if this.head.next == this.tail {
        return nil
    }
    first := this.head.next
    this.remove(first)
    return first
}

type Solution struct {
    capacity int 
    knmap map[int]*Node
    cache *DoubleLinkedList
}

func Constructor(capacity int) Solution {
    lruCache := Solution {
        capacity : capacity,
        knmap : map[int]*Node{},
        cache : initDoubleLinkedList(),
    }
    return lruCache
}
func (this *Solution) makeRecently (key int) {
    node := this.knmap[key]
    this.cache.remove(node)
    this.cache.addLast(node)
}
func (this *Solution) addRecently (key, value int) {
    node := initNode(key, value)
    this.cache.addLast(node)
    this.knmap[key] = node
}
func (this *Solution) deletekey(key int)  {
    node := this.knmap[key]
    this.cache.remove(node)
    delete(this.knmap, key)
}
func (this *Solution) deleteLRU() {
    deleteLRU := this.cache.removeFirst()
    delete(this.knmap, deleteLRU.key)
}
func (this *Solution) get(key int) int {
    node, exist := this.knmap[key]
    if !exist {
        return -1
    }
    this.makeRecently(key)
    return node.value
}


func (this *Solution) set(key int, value int)  {
    _, exist := this.knmap[key]
    if exist {
        this.deletekey(key)
        this.addRecently(key, value)
    }else {
        if this.cache.size == this.capacity {
            this.deleteLRU()
        }
        this.addRecently(key, value)
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * solution := Constructor(capacity);
 * output := solution.get(key);
 * solution.set(key,value);
 */