146. LRU 缓存机制(困难)

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

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 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 <= 104
最多调用 3 * 104 次 get 和 put

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache

思路：

hashmap+双向链表

思路

借助LinkedHashMap

  • get：如果不存在，返回-1，如果存在，将其变成最近使用，返回该值
  • put：如果key已经存在，这里需要注意，需要更新值，然后变成最近使用；如果不存在，此时如果cache容量已经满了，将最近未使用的删除，再将新值添加进cache

代码1：

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class LRUCache {
    int cap;//容量
    HashMap<Integer, Node> map;//用以寻找
    DoubleLinkedList cache;//用以实现lru
    public LRUCache(int capacity) {
        map = new HashMap<>();
        cache = new DoubleLinkedList();
        cap = capacity;
    }

    public int get(int key) {

        if(!map.containsKey(key)){
            return -1;
        }
        //获取到需要的值
        int value = map.get(key).val;
        //放到最近使用（队头）
        put(key,value);
        return value;
    }

    public void put(int key, int value) {
        Node node = new Node(key,value);
        //是否存在
        if(map.containsKey(key)){
            cache.deleteNode(map.get(key));
            cache.addFirst(node);
            //将新的节点加进去
            map.put(key,node);
        }else{
            //是否超出容量
            if(map.size()==cap){
                int k = cache.deleteLast();
                map.remove(k);
            }
            //直接添加到队头
            cache.addFirst(node);
            map.put(key,node);
        }
    }



}
//自定义双向链表，需要的功能：队头添加元素，队尾删除元素，删除特定元素
class DoubleLinkedList{
    //定义头尾节点
    Node head,tail;
    //初始化
    DoubleLinkedList(){
        head = new Node(0,0);
        tail = new Node(0,0);
        //队头指向队尾
        head.next = tail;
        //队尾指向队头
        tail.prev = head;
    }
    //队头添加
    public void addFirst(Node node){
        //该节点指向头节点的next
        node.next = head.next;
        node.prev = head;

        head.next.prev = node;
        head.next = node;
    }
    //删除对应元素
    public int deleteNode(Node node){
        int key = node.key;//必须要先获取
        node.next.prev = node.prev;
        node.prev.next = node.next;
        return key;
    }
    //删除队尾元素
    public int deleteLast(){
        if(head.next==tail){
            return -1;
        }
        return deleteNode(tail.prev);
    }
}
//Node,具有双向的指针
class Node{
    int key;
    int val;
    Node prev;
    Node next;

    //初始化
    public Node(int key,int val){
        this.key = key;
        this.val = val;
    }
}

作者：venturekwok
链接：https://leetcode-cn.com/problems/lru-cache/solution/zui-jin-mian-zi-jie-yi-mian-peng-dao-lia-1t15/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码2：

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
class LRUCache {
    int cap;//容量
    LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        cap = capacity;
    }

    public int get(int key) {
        //若数据不在cache中，返回-1
        if(!cache.containsKey(key)){
            return -1;
        }
        makeRecently(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        //如果key存在
        if(cache.containsKey(key)){
            //这里有问题，需要添加一个更新
            cache.put(key,value);
            //升级为最近使用
            makeRecently(key);
            return;
        }
        //如果容量满了
        if(cache.size()>=cap){
            //链表头部就是最久未使用的key
            int oldkey = cache.keySet().iterator().next();
            cache.remove(oldkey);
        }
        //加入
        cache.put(key,value);
    }
    //变成最近使用
    void makeRecently(int key){
        int value = cache.get(key);
        //将数删除，并重新插入到尾部
        cache.remove(key);
        cache.put(key,value);
    }
}