146. LRU 缓存机制

146. LRU 缓存机制

题意

通过哈希表和双向链表实现LRU机制
什么是LRU：https://zhuanlan.zhihu.com/p/34133067

题解

思路：只要想清楚LRU的过程就好

• GET：
  • 不存在：直接返回-1
  • 存在：将node移到head，返回value
• PUT：
  • 存在：将value更新，将node移到head
  • 不存在：新建node，更新hash，将node插到head，再判断len有没有超出，超出则移除tail
• 注意点：
  • 为什么需要head和tail节点：不用再考虑左右越界问题
  • 为什么双向链表需要存key：在删除尾节点的时候需要根据节点的key删除hash中的元素

复杂度：

• 时间复杂度：O(1)
• 空间复杂度：O(容量) ```go type LRUCache struct { cache map[int]DLinkedNode head, tail DLinkedNode len, cap int }

type DLinkedNode struct { key, value int prev, next *DLinkedNode }

func initDLinkedNode(key, value int) *DLinkedNode { return &DLinkedNode{ key: key, value: value, } }

func (this LRUCache) addToHead(node DLinkedNode) { node.prev = this.head node.next = this.head.next this.head.next.prev = node this.head.next = node }

func (this LRUCache) removeNode(node DLinkedNode) { node.prev.next = node.next node.next.prev = node.prev }

func (this LRUCache) moveToHead(node DLinkedNode) { this.removeNode(node) this.addToHead(node) }

func (this LRUCache) removeTail() DLinkedNode { node := this.tail.prev this.removeNode(node) return node }

func Constructor(capacity int) LRUCache { lru := LRUCache{ cache: map[int]*DLinkedNode{}, head: initDLinkedNode(0, 0), tail: initDLinkedNode(0, 0), cap: capacity, } lru.head.next = lru.tail lru.tail.prev = lru.head return lru }

func (this *LRUCache) Get(key int) int { node, ok := this.cache[key] if !ok { return -1 } this.moveToHead(node) return node.value }

func (this *LRUCache) Put(key int, value int) { node, ok := this.cache[key] if ok { node.value = value this.moveToHead(node) return } newNode := initDLinkedNode(key, value) this.cache[key] = newNode this.addToHead(newNode) this.len++ if this.len > this.cap { tailNode := this.removeTail() delete(this.cache, tailNode.key) this.len— } }

``` 结果：

• 执行用时：112 ms, 在所有 Go 提交中击败了94.04%的用户
• 内存消耗：11.6 MB, 在所有 Go 提交中击败了90.58%的用户