题解 | #设计LRU缓存结构 list + map#

我们通过 map + list 的方式实现LRU

我们需要额外记录两个值

• nbytes 表示当前使用的内存
• capacity 表示当前的容量

我们为了方便额外记录一个 entry 记录一下key 和 value ,方便删除map中的值

package main
import "container/list"
type Solution struct {
     // write code here
     nbytes   int
     capacity int
     ll    *list.List
     cache map[int]*list.Element
}
type entry struct{
    key int
    value int
}

func Constructor(capacity int) Solution {
    // write code here
    return Solution{
        capacity: capacity,
        ll: list.New(),
        cache: make(map[int]*list.Element),
    }
}


func (this *Solution) get(key int) int {
    // write code here
    if ele , ok := this.cache[key]; ok {
        this.ll.MoveToFront(ele);
        kv := ele.Value.(*entry);
        return kv.value
    }
    return -1
}

func (this *Solution) Remove(){
    ele := this.ll.Back()

    if ele != nil {
        this.ll.Remove(ele)
        kv := ele.Value.(*entry)
        this.nbytes -= 1;
        delete(this.cache,kv.key)
    }
}
func (this *Solution) set(key int, value int)  {
    // write code here
    if ele,ok := this.cache[key]; ok {
        this.ll.MoveToFront(ele) 
        kv := ele.Value.(*entry)
        kv.value = value
    }else{
        this.nbytes += 1;
        ele := this.ll.PushFront(&entry{key , value})
        this.cache[key] = ele
    }
    for this.capacity != 0 && this.capacity < this.nbytes {
        this.Remove()
    }
}