公众号merlinsea
- 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
- LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1，golang可以返回多关键字，用于标识是否存在
- void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字
- 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行
- 解题思路
- 首先要求get(key)需要在O(1)的时间复杂度下获取结果，因此这里可以使用map来存储数据，map的key是一个int类型，map的value是一个地址，这个地址指向真正的节点。
- 另外由于put操作中在数据量超过capacity的时候需要把最久没有使用到的关键字删除，因此可以知道还需要使用双向链表来记录数据。
- 当put操作的时候发现lru缓存的容量已经满了的情况，需要将tail 的前驱节点（即最久没有访问过的节点）删除。 这里的双向链表采用了虚拟头节点和尾节点的编程技巧。
- 为什么使用双向链表
- 双向链表每个节点都有前驱和后继节点，可以通过链表的顺序关系可以来判断哪些节点是最近使用的，哪些节点是最早使用的。
- 双向链表中删除某个节点可以保证O(1)的时间复杂度，首先在map中通过key快速定位下节点信息，得到节点信息以后可以把这个节点通过调整指针指向来使其移动到链表中的第一位【表示最近访问过了】。
- 代码实现
package lru_cache // 定义双向链表的节点 type Node struct { Key int Val int Pre *Node Next *Node } // lru缓存 type LRUCache struct { KeyNodeMap map[int]*Node Head *Node Tail *Node Capacity int } // 构造器，通过new()可以创建一个指向结构体的指针 func Constructor(capacity int) LRUCache { lruCathe := LRUCache{ KeyNodeMap: make(map[int]*Node), Head: new(Node), Tail: new(Node), Capacity: capacity, } lruCathe.Head.Next = lruCathe.Tail lruCathe.Tail.Pre = lruCathe.Head return lruCathe } func (this *LRUCache) Get(key int) int { nodePtr, ok := this.KeyNodeMap[key] if !ok { return -1 } // 将结果放到第一个 this.moveFirst(nodePtr) return nodePtr.Val } func (this *LRUCache) Put(key int, value int) { // 判断是否存在 nodePtr, ok := this.KeyNodeMap[key] if ok { // 存在则进行替换 nodePtr.Val = value // 将节点移到最前面 this.moveFirst(nodePtr) } else { if this.Capacity == len(this.KeyNodeMap) { // 容量已经满了，先删除tail（包括双向链表和map） oldNodePtr := this.Tail.Pre this.Tail.Pre = oldNodePtr.Pre oldNodePtr.Pre.Next = this.Tail delete(this.KeyNodeMap, oldNodePtr.Key) } // 插入 nodePtr := &Node{ Key: key, Val: value, Pre: this.Head, Next: this.Head.Next, } this.Head.Next.Pre = nodePtr this.Head.Next = nodePtr this.KeyNodeMap[key] = nodePtr } } // 将节点nodePtr移动的第一位表示最近访问过的节点 func (this *LRUCache) moveFirst(nodePtr *Node) { nodePtr.Pre.Next = nodePtr.Next nodePtr.Next.Pre = nodePtr.Pre nodePtr.Next = this.Head.Next this.Head.Next.Pre = nodePtr this.Head.Next = nodePtr nodePtr.Pre = this.Head }
func main() { lruCache := lru_cache.Constructor(2) lruCache.Put(1, 1) lruCache.Put(2, 2) v := lruCache.Get(1) fmt.Println(v) lruCache.Put(3, 3) v = lruCache.Get(2) fmt.Println(v) lruCache.Put(4, 4) v = lruCache.Get(1) fmt.Println(v) v = lruCache.Get(3) fmt.Println(v) v = lruCache.Get(4) fmt.Println(v) }
golang版本永久算法题训练营～～
奔跑的小梁，公众号：梁霖编程工具库
