力扣146. LRU 缓存

Problem: 146. LRU 缓存

题目描述

思路

主要说明大致思路，具体实现看代码。

1.为了实现题目中的O(1)时间复杂度的get与put方法，我们利用哈希表和双链表的结合，将key作为键，对应的链表的节点作为值（也就是在此处我们用一个节点类作为值）；
2.定义双链表的节点类，其中包含每次put的键与对应的值，还包括前驱、后驱指针；
3.编写双链表的实现类，并实现：

3.1.初始化一个双链表(创建虚拟头、尾节点；由于我们要实现将最就不使用的节点删除，我们在此使用尾插法即每次链表尾部位最近使用的，表头为最久不适用的)；
3.2.实现尾插一个节点；
3.3.实现删除一个给定的节点；
3.4.实现从表头删除一个节点（删除最久不使用的节点）
3.5.返回链表的长度

4.实现LRUCache类：

4.1. 创建哈希表map与双链表cache；
4.2. 为了不直接在get与put中对map与cache操作带来麻烦（主要操作是同步在mao中添加key同时在cache中增、删、改对应节点的值），我们封装实现一些API（具体操作实现看代码）
4.3. 实现get与put方法（直接看代码）

复杂度

时间复杂度:

$O(n)$;其中$n$为要操作的次数

空间复杂度:

$O(n)$

Code

/**
 * Node class
 */
class Node {
    public int key;
    public int val;
    public Node next;
    public Node prev;

    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}

class DoubleList {
    //The dummy node of head and tail to a double linked list
    private Node head;
    private Node tail;
    //The size of a linked list
    private int size;

    public DoubleList() {
        //Initialize the element of double linked list
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // Add node x at the end of the list, time O(1)
    // Tail insertion method of bidirectional linked list
    // with virtual head and tail nodes
    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    // Delete the x node in the linked list (x must exist)
    // Since it is a double-linked list and given to the target Node,
    // time O(1)
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    // Delete the first node in the linked list
    // and return the node, time O(1)
    public Node removeFirst() {
        if (head.next == null) {
            return null;
        }
        Node first = head.next;
        remove(first);
        return first;
    }

    // Return list length, time O(1)
    public int size() {
        return size;
    }
}

class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    //Max capacity
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    // Upgrade a key to the most recently used
    private void makeRecently(int key) {
        Node x = map.get(key);
        // Delete this node from the linked list first
        cache.remove(x);
        // Move back to the end of the line
        cache.addLast(x);
    }

    // Add the most recently used element
    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        // The end of the list is the most recently used element
        cache.addLast(x);
        // Add the mapping of the key to the map
        map.put(key, x);
    }

    // Delete a key
    private void deleteKey(int key) {
        Node x = map.get(key);
        // Delete from the linked list
        cache.remove(x);
        // Delete from map
        map.remove(key);
    }

    // Delete the element that has been unused the longest
    private void removeLeastRecently() {
        // The first element at the head of the list is the one
        // that has been unused for the longest time
        Node deletedNode = cache.removeFirst();
        // Delete its key from the map
        int deleteKey = deletedNode.key;
        map.remove(deleteKey);
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // Upgrade the data to the most recently used
        makeRecently(key);
        return map.get(key).val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // Delete old data
            deleteKey(key);
            // The newly inserted data is the latest data
            addRecently(key, value);
            return;
        }
        if (cap == cache.size()) {
            // Delete the element that has been unused the longest
            removeLeastRecently();
        }
        // Add as recently used element
        addRecently(key, value);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149