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 解法