LeetCode146 动手实现LRU算法

146. LRU缓存机制

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

解题思路

• LRU是Least Recently Used的缩写,即"最近最少使用",也就是说,LRU缓存把最近最少使用的数据移除,让给最新读取的数据
• 往往最常读取的,也是读取次数最多的
• 操作系统等最常使用的缓存策略,即LRU
• 需要在O(1)时间复杂度实现put操作,就需要使用双向链表,方便移动节点(单链表无法达到O(1))
• O(1)实现get查询操作,就需要使用map存key-node键值对,实现快速查询
• 具体详见代码注释

代码实现

// doublyLinkedNode defines a node for double-linked-list
type doublyLinkedNode struct {
 prev, next *doublyLinkedNode
 key, val int
}
// LRUCache defines a object for cache
type LRUCache struct {
 len, cap int
 first, last *doublyLinkedNode //head,tail
 nodes map[int]*doublyLinkedNode //hashtable,find node in O(1)
}
// Constructor creates a cache object
func Constructor(capacity int) LRUCache {
 return LRUCache{
 len: 0,
 cap: capacity,
 first: nil,
 last: nil,
 nodes: make(map[int]*doublyLinkedNode, capacity),
 }
}
// Get returns value by key
func (l *LRUCache) Get(key int) int {
 if node, ok := l.nodes[key]; ok {
 //key exist
 // move the node to the head of double-linked-list
 l.moveToFirst(node)
 return node.val
 }
 //key not exist,return -1
 return -1
}
// Put puts key-value pair into LRUCache
func (l *LRUCache) Put(key int, value int) {
 if node, ok := l.nodes[key]; ok {
 //update value of old node
 node.val = value
 // move the node to the head of double-linked-list
 l.moveToFirst(node)
 } else {
 if l.len == l.cap {
 delete(l.nodes, l.last.key)
 l.removeLast()
 } else {
 l.len++
 }
 node := &doublyLinkedNode{
 prev: nil,
 next: nil,
 key: key,
 val: value,
 }
 l.nodes[key] = node
 l.insertToFirst(node)
 }
}
func (l *LRUCache) removeLast() {
 if l.last.prev != nil {
 //双向链表长度>1
 l.last.prev.next = nil
 } else {
 //双向链表长度 == 1,first == last
 l.first = nil
 }
 l.last = l.last.prev
}
func (l *LRUCache) moveToFirst(node *doublyLinkedNode) {
 switch node {
 case l.first:
 return
 case l.last:
 l.removeLast()
 default:
 //在双向链中,删除 node 节点
 node.prev.next = node.next
 node.next.prev = node.prev
 }
 // 策略是
 // 如果是移动node
 // 先删除,再插入
 l.insertToFirst(node)
}
func (l *LRUCache) insertToFirst(node *doublyLinkedNode) {
 if l.last == nil {
 //空的双向链表
 l.last = node
 } else {
 node.next = l.first
 l.first.prev = node
 }
 l.first = node
}

GitHub

• 源码在这里
• 项目中会提供各种数据结构及算法的Golang实现,以及 LeetCode 解法

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传