福哥答案2020-09-18：
方法：哈希表 + 双向链表。
时间复杂度：对于 put 和 get 都是 O(1)。
空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。
代码用go语言编写，代码如下：
package test40_lru import (
"fmt"
"testing"
) /*
哈希表 + 双向链表
时间复杂度：对于 put 和 get 都是 O(1)O(1)。
空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。
*/
//https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
//go test -v -test.run TestLru
func TestLru(t *testing.T) {
cache := NewLRUCache(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 } type LRUCache struct {
size int
capacity int
cache map[int]*DLinkedNode
head, tail *DLinkedNode
} type DLinkedNode struct {
key, value int
prev, next *DLinkedNode
} func NewDLinkedNode(key, value int) *DLinkedNode {
return &DLinkedNode{
key: key,
value: value,
}
} func NewLRUCache(capacity int) LRUCache {
l := LRUCache{
cache: map[int]*DLinkedNode{},
head: NewDLinkedNode(0, 0),
tail: NewDLinkedNode(0, 0),
capacity: capacity,
}
l.head.next = l.tail
l.tail.prev = l.head
return l
} //获取元素
func (f *LRUCache) Get(key int) int {
//如果缓存里未找到元素
if _, ok := f.cache[key]; !ok {
fmt.Println(-1)
return -1
} //缓存里有元素
node := f.cache[key] //如果 key 存在，先通过哈希表定位，再移到头部
f.moveToHead(node)
fmt.Println(node.value)
return node.value
} //放入元素
func (f *LRUCache) Put(key int, value int) {
//如果缓存里没有元素
if _, ok := f.cache[key]; !ok {
node := NewDLinkedNode(key, value)
f.cache[key] = node
//放在头部
f.addToHead(node)
f.size++
//如果元素个数大于容量，需要删除元素
if f.size > f.capacity {
//删除链表尾部
removed := f.removeTail()
//删除map中的key
delete(f.cache, removed.key)
f.size--
}
} else { //缓存里有元素
//获取元素
node := f.cache[key]
//修改值
node.value = value
//移动到链表头
f.moveToHead(node)
}
} //添加到头节点
func (f *LRUCache) addToHead(node *DLinkedNode) {
node.prev = f.head
node.next = f.head.next
f.head.next.prev = node
f.head.next = node
} //删除节点
func (f *LRUCache) removeNode(node *DLinkedNode) {
node.prev.next = node.next
node.next.prev = node.prev
} //移动到头节点
func (f *LRUCache) moveToHead(node *DLinkedNode) {
f.removeNode(node)
f.addToHead(node)
} //删除尾部
func (f *LRUCache) removeTail() *DLinkedNode {
node := f.tail.prev
f.removeNode(node)
return node
}
执行结果如下：
