146. LRU 缓存

mid

请你设计并实现一个满足 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, Val int
	Next     *Node
	Prev     *Node
}

type LinkList struct {
	Head, Tail *Node
}

func NewLinkList() *LinkList {
	res := LinkList{Head: &Node{}, Tail: &Node{}}
	res.Head.Next = res.Tail
	res.Tail.Prev = res.Head
	return &res
}

func (l *LinkList) AddToHead(n *Node) {
	l.Head.Next.Prev = n
	n.Next = l.Head.Next
	l.Head.Next = n
	n.Prev = l.Head
}

func (l *LinkList) MoveToHead(n *Node) {
	n.Prev.Next = n.Next
	n.Next.Prev = n.Prev

	l.Head.Next.Prev = n
	n.Next = l.Head.Next
	l.Head.Next = n
	n.Prev = l.Head

}

func (l *LinkList) RemoveTail() int {
	n := l.Tail.Prev
	l.Tail.Prev = n.Prev
	n.Prev.Next = l.Tail
	return n.Key
}

type LRUCache struct {
	HashMap  map[int]*Node
	LinkList *LinkList
	Capacity int
	Size     int
}

func Constructor(capacity int) LRUCache {
	res := LRUCache{HashMap: make(map[int]*Node), LinkList: NewLinkList()}
	return res
}

func (this *LRUCache) Get(key int) int {
	if _, ok := this.HashMap[key]; !ok {
		return -1
	} else {
		node := this.HashMap[key]
		// 命中，移至最前
		this.LinkList.MoveToHead(node)
		return node.Val
	}
}

func (this *LRUCache) Put(key int, value int) {
	if _, ok := this.HashMap[key]; !ok {
		// 不存在
		node := Node{Key: key, Val: value}
		this.HashMap[key] = &node
		this.LinkList.AddToHead(&node)
		this.Size++
		if this.Size > this.Capacity {
			// 溢出，淘汰最末
			removedKey := this.LinkList.RemoveTail()
			delete(this.HashMap, removedKey)
			this.Size--
		}
	} else {
		// 存在，修改其值
		node := this.HashMap[key]
		node.Val = value
		// 命中，移至最前
		this.LinkList.MoveToHead(node)
	}
}

146. LRU 缓存

哈希表 + 双向链表​

哈希表 + 双向链表