LeetCode:LRU 缓存机制


题目

前言:

推荐官方题解:https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/

注:对高性能的 LRU 理解,会有一定提升作用

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制

实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • · 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 3000
  • 0 <= value <= 10^4
  • 最多调用 3 * 104getput

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lru-cache

代码

Go

如下题解:性能无官方性能优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package main

import "fmt"

type LRUCache struct {
Capacity int
Keys []int
Items map[int]int
}

func Constructor(capacity int) *LRUCache {
return &LRUCache{capacity, []int{}, map[int]int{}}
}

func (this *LRUCache) Get(key int) int {
_, value := this.Has(key)

return value
}

func (this *LRUCache) Put(key int, value int) {
if ok, _ := this.Has(key); !ok {
this.Clean()
this.Keys = append(this.Keys, key)
}

this.Items[key] = value
}

func (this *LRUCache) Has(key int) (bool, int) {
if value, ok := this.Items[key]; ok {
if index := indexOf(key, this.Keys); index >= 0 {
this.Keys = append(this.Keys[0:index], this.Keys[(index+1):]...)
this.Keys = append(this.Keys, key)
}

return true, value
}

return false, -1
}

func (this *LRUCache) Clean() {
if len(this.Keys) >= this.Capacity {
first := this.Keys[0]

this.Keys = this.Keys[1:]
delete(this.Items, first)
}
}

func indexOf(value int, items []int) int {
for k, v := range items {
if v == value {
return k
}
}

return -1
}

func main() {
cache := Constructor(2)
// cache.Put(1, 1)
// cache.Put(2, 2)
// cache.Put(3, 3)
// cache.Put(4, 4)
// cache.Put(3, 5)

cache.Put(1, 1)
cache.Put(2, 2)
cache.Get(1)
// cache.Put(3, 3)
// cache.Get(2)

fmt.Println(cache)
}

评论