Leetcode专题-146-LRU 缓存

ChatGPT 可用网址，仅供交流学习使用，如对您有所帮助，请收藏并推荐给需要的朋友。
https://ckai.xyz

leetcode链接：
https://leetcode.cn/problems/lru-cache/
解题思路：

// entry 缓存节点
type entry struct {
    key int
    value int
}

// LRUCache .
type LRUCache struct {
    cap int
    cache map[int]*list.Element
    lst  *list.List
}

// Constructor . 
func Constructor(capacity int) LRUCache {
    return LRUCache{
        cap: capacity,
        cache: map[int]*list.Element{},
        lst: list.New(),
    }
}

// Get 获取元素
func (this *LRUCache) Get(key int) int {
   e := this.cache[key]
   if e == nil {
       return -1
   }
   this.lst.MoveToFront(e) // 将最近使用的节点置于链表头
   return e.Value.(entry).value
}

// Put 写入元素
func (this *LRUCache) Put(key int, value int)  {
    // 首先判断key是否已经存在
    if e:=this.cache[key]; e != nil {
        // key存在的情况下，更新值并置于列表头
        e.Value = entry{key, value}
        this.lst.MoveToFront(e)
        return
    }
    // key不存在的情况下，直接在头节点加入元素
    this.cache[key] = this.lst.PushFront(entry{key, value})
    // 缓存空间满时，淘汰最旧的缓存
    if len(this.cache) > this.cap {
        delete(this.cache, this.lst.Remove(this.lst.Back()).(entry).key)
    }
}