LRU

双向链表 + Hash表

链表存储顺序, Hash 表可以用 o(1) 时间复杂度查询链表中的 Node 地址

实现

package main

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/

type doublyLinkList struct {
    pre *doublyLinkList
    next *doublyLinkList
    val int
    mkey int
}

type LinkedHashMap struct {
    head *doublyLinkList
    tail *doublyLinkList
    length int
    capacity int
    hash map[int]*doublyLinkList
}

func NewLinkedHashMap(capacity int) *LinkedHashMap {
    l := &LinkedHashMap{
        head: new(doublyLinkList),
        tail: new(doublyLinkList),
        capacity: capacity,
        hash: make(map[int]*doublyLinkList, 0),
    }
    l.head.next = l.tail
    l.tail.pre = l.head
    return l
}

func (this *LinkedHashMap) Set(key, value int) {
    _, ok := this.hash[key]
    if !ok {
        if this.length >= this.capacity {
            last := this.tail.pre
            last.pre.next = this.tail
            this.tail.pre = last.pre
            delete(this.hash, last.mkey)
            this.length--
        }
        node := &doublyLinkList{
            pre: this.head,
            next: this.head.next,
            val: value,
            mkey: key,
        }
        this.head.next = node
        node.next.pre = node
        this.hash[key] = node
        this.length++
    } else {
        this.MoveNodeToHead(key)
    }
}

func (this *LinkedHashMap) Get(key int) int {
    pNode, ok := this.hash[key]
    if ok {
        this.MoveNodeToHead(key)
        return pNode.val
    } else {
        return -1
    }
}

func (this *LinkedHashMap) MoveNodeToHead(key int) {
    node := this.hash[key]
    node.next.pre = node.pre
    node.pre.next = node.next
    node.next = this.head.next
    node.pre = this.head
    this.head.next = node
    node.next.pre = node
}

func LRU( operators [][]int ,  k int ) []int {
    // write code here
    if k <=0 {
        return []int{}
    }
    list := NewLinkedHashMap(k)
    result := make([]int, 0)
    for _, v := range operators {
        switch v[0] {
            case 1:
            list.Set(v[1], v[2])
            break
            case 2:
            result = append(result, list.Get(v[1]))
            break
        } 
    }
    return result

}