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

import "container/list"

type LRUCache struct {
	Len        int                      // 大小
	Value      map[int]int              // value存放 
	LruIndex   map[int]*list.Element    // key 到 链表节点的映射
	Lru       *list.List                // 维护最近访问顺序的链表
}

func (l *LRUCache) set(k, v int) {
	if l.Lru.Len() >= l.Len {
		k := l.Lru.Back().Value.(int)
		delete(l.Value, k)
		delete(l.LruIndex, k)
		l.Lru.Remove(l.Lru.Back())
	}
	l.Value[k] = v
	l.LruIndex[k] = l.Lru.PushFront(k)
}

func (l *LRUCache) get(k int) int {
	if v, ok := l.Value[k]; ok {
		l.Lru.MoveToFront(l.LruIndex[k])
		return v
	}
	return -1
}

func LRU( operators [][]int ,  k int ) []int {
	lru := &LRUCache{
		Len: k,
		Value: make(map[int]int),
        LruIndex: make(map[int]*list.Element),
		Lru: list.New(),
	}

	ret := make([]int, 0)
	for _, v := range operators {
		if v[0] == 1 {
			lru.set(v[1], v[2])
		}
		if v[0] == 2 {
			ret = append(ret, lru.get(v[1]))
		}
	}
	return ret
}