LRU 缓存

力扣 146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类： LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

方案一：结合无序映射和双向链表。

type node struct {
    key  int
    val  int
    pre  *node
    next *node
}

func deleteNode(cur *node) {
    cur.pre.next = cur.next
    cur.next.pre = cur.pre
}

func insertNode(head, cur *node) {
    cur.next = head.next
    cur.pre = head
    head.next.pre = cur
    head.next = cur
}

type LRUCache struct {
    head     *node          // 双向链表头节点，最近使用过的节点都会跟在头节点后
    tail     *node          // 双向链表尾节点
    cache    map[int]*node  // 无序映射保存 key 和对应节点指针
    capacity int            // 容量       
}


func Constructor(capacity int) LRUCache {
    head, tail := &node{}, &node{}
    head.next, tail.pre = tail, head
    return LRUCache{
        head:     head,
        tail:     tail,
        cache:    make(map[int]*node),
        capacity: capacity,
    }
}


func (this *LRUCache) Get(key int) int {
    return this.get(key)
}

func (this *LRUCache) get(key int) int {
    // 判断节点是否存在
    cur, ok := this.cache[key]
    if !ok {
        return -1
    }

    // 删除当前节点，而后将其重新插入头节点
    deleteNode(cur)
    insertNode(this.head, cur)
    return cur.val
}

func (this *LRUCache) Put(key int, value int)  {
    // 判断当前节点是否存在
    if this.get(key) != -1 {
        // 存在，更新节点 value
        this.cache[key].val = value
        return
    }
    
    // key 相关节点不存在
    // 构建节点
    cur := &node{
        key: key,
        val: value,
    }
    // 当前 LRU 容量已满
    if len(this.cache) == this.capacity {
        // 找出最近最少使用的节点
        least := this.tail.pre
        // 删除最少使用的节点信息
        delete(this.cache, least.key)
        deleteNode(least)
    } 

    // 加入新节点信息
    this.cache[key] = cur
    insertNode(this.head, cur)
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

LRU 缓存

力扣 146. LRU 缓存

CATALOG

FEATURED TAGS