算法题：146. LRU 缓存时间击败89%空间击败98.75%（题目+思路+代码+注释）

悠悠 2024-04-01 09:42 7阅读 0赞

![在这里插入图片描述][8218bf5a0b3140d6a072fb47d7cbb20a.png]

### 题目 ###

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。  
实现 LRUCache 类：  
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存  
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。  
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。  
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入  
\[“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 <= 10000  
0 <= value <= 105  
最多调用 2 \* 105 次 get 和 put

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/lru-cache  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 思路 ###

LRU算法要实现O（1）级的时间复杂度则必须试用过哈希来快速查找，而LRU有容量，那么在缓存淘汰时则必须去删除某个节点，并且确定删除的是最近未使用的缓存，要实现最近未使用只能使用双向链表来实现，由哈希表指向链表节点，用来快速定位，使用时将节点剔除并移动到最后面，淘汰时剔除链表最前面的节点，因为每次使用或插入新的就会把相关节点挪到最后面去，这样就实现了O（1）的时间复杂度的LRU算法。  
总之，利用链表添加删除的O（1）和哈希的O（1）查找能力实现整个时间复杂度O(1)的LRU算法

### 代码 ###

*  提交的代码

import java.util.HashMap;
    import java.util.Map;
    public class LRUCache {
        
    
        private Map<Integer, Node> map;
        private Node first;
        private Node last;
        private int capacity;
    
    
        public LRUCache(int capacity) {
        
            this.capacity = capacity;
            map = new HashMap<>(capacity);
        }
    
    
        private void add(Node node) {
        
            node.pre = last;
            last = node;
            if (node.pre != null) {
        
                node.pre.next = node;
            }
            if (first == null) {
        
                first = last;
            }
        }
    
    
    
        private Node poll() {
        
            Node pop = first;
            if (first == null) {
        
                return null;
            }
            first = first.next;
            if (first != null) {
        
                first.pre = null;
            }
            if (first == pop) {
        
                first = last = null;
            }
            return pop;
        }
    
    
        private void unlink(Node node) {
        
            Node pre = node.pre;
            Node next = node.next;
            if (pre != null) {
        
                pre.next = next;
            } else {
        
                first = next;
            }
            if (next != null) {
        
                next.pre = pre;
            } else {
        
                last = pre;
            }
            if (first != null) {
        
                first.pre = null;
            }
            if (last != null) {
        
                last.next = null;
            }
            if (first == node) {
        
                first = null;
            }
            if (last == node) {
        
                last = null;
            }
            node.next = node.pre = null;
        }
    
       
    
        public int get(int key) {
        
            Node node = map.get(key);
            // 使用过
            if (node != null) {
        
                unlink(node);
                add(node);
            }
            return node != null ? node.val : -1;
        }
    
        public void put(int key, int value) {
        
            Node node = map.get(key);
            if (node == null) {
        
                if (capacity == map.size()) {
        
                    // 需要淘汰一个
                    Node pop = poll();
                    map.remove(pop.key);
                }
                // 放入新的
                node = new Node(key, value);
                map.put(key, node);
            } else {
        
                // 覆盖
                node.val = value;
                unlink(node);
            }
            add(node);
        }
    
    
    }
    
    class Node {
        
        int key;
        int val;
        Node pre;
        Node next;
    
        public Node(int key, int val) {
        
            this.key = key;
            this.val = val;
        }
    }
    /**
     * 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);
     */

*  调试时用的代码

package leetcode.q146;
    
    import org.junit.Test;
    
    import java.util.HashMap;
    import java.util.Map;
    
    public class LRUCache {
        
    
        private Map<Integer, Node> map;
        private Node first;
        private Node last;
        private int capacity;
    
    
        public LRUCache(int capacity) {
        
            this.capacity = capacity;
            map = new HashMap<>(capacity);
        }
    
        public static void main(String[] args) {
        
            LRUCache lruCache = new LRUCache(2);
            lruCache.put(1, 0);
            lruCache.print();
            lruCache.put(2, 2);
            lruCache.print();
            System.out.println(lruCache.get(1));
            lruCache.print();
            lruCache.put(3, 3);
            System.out.println(lruCache.get(2));
            lruCache.put(4, 4);
            System.out.println(lruCache.get(1));
            System.out.println(lruCache.get(3));
            System.out.println(lruCache.get(4));
        }
    
        private void add(Node node) {
        
            node.pre = last;
            last = node;
            if (node.pre != null) {
        
                node.pre.next = node;
            }
            if (first == null) {
        
                first = last;
            }
            System.out.println("添加" + node.val + "后");
            print();
        }
    
        @Test
        public void testAdd() {
        
            print();
            add(new Node(1, 1));
            add(new Node(2, 2));
            add(new Node(3, 3));
            add(new Node(4, 4));
        }
    
        @Test
        public void testPoll() {
        
            print();
            add(new Node(1, 1));
            poll();
            poll();
            add(new Node(2, 2));
            add(new Node(3, 3));
            poll();
            poll();
            poll();
            add(new Node(4, 4));
            add(new Node(4, 4));
            add(new Node(4, 4));
            poll();
            add(new Node(4, 4));
            poll();
            poll();
            print();
        }
    
    
        private void print() {
        
            Node p = first;
            System.out.print("链表:");
            while (p != null) {
        
                if (p != first) {
        
                    System.out.print("->");
                }
                System.out.print(p.val);
                p = p.next;
            }
            System.out.println();
        }
    
        private Node poll() {
        
            Node pop = first;
            if (first == null) {
        
                System.out.println("弹出null");
                return null;
            }
            first = first.next;
            if (first != null) {
        
                first.pre = null;
            }
            if (first == pop) {
        
                first = last = null;
            }
            System.out.println("弹出" + pop.val);
            return pop;
        }
    
        /**
         * A A
         * A B
         * A B C
         *
         * @param node
         */
        private void unlink(Node node) {
        
            Node pre = node.pre;
            Node next = node.next;
            if (pre != null) {
        
                pre.next = next;
            } else {
        
                first = next;
            }
            if (next != null) {
        
                next.pre = pre;
            } else {
        
                last = pre;
            }
            if (first != null) {
        
                first.pre = null;
            }
            if (last != null) {
        
                last.next = null;
            }
            if (first == node) {
        
                first = null;
            }
            if (last == node) {
        
                last = null;
            }
            node.next = node.pre = null;
        }
    
        @Test
        public void testUnlink() {
        
            add(new Node(1, 1));
            unlink(first);
            print();
            add(new Node(1, 1));
            add(new Node(2, 2));
            unlink(first);
            print();
            unlink(first);
            print();
            add(new Node(1, 1));
            add(new Node(2, 2));
            unlink(last);
            print();
            add(new Node(1, 1));
            Node node = new Node(2, 2);
            add(node);
            add(new Node(3, 3));
            unlink(node);
            print();
        }
    
        public int get(int key) {
        
            Node node = map.get(key);
            // 使用过
            if (node != null) {
        
                unlink(node);
                add(node);
            }
            return node != null ? node.val : -1;
        }
    
        public void put(int key, int value) {
        
            Node node = map.get(key);
            if (node == null) {
        
                if (capacity == map.size()) {
        
                    // 需要淘汰一个
                    Node pop = poll();
                    map.remove(pop.key);
                }
                // 放入新的
                node = new Node(key, value);
                map.put(key, node);
            } else {
        
                // 覆盖
                node.val = value;
                unlink(node);
            }
            add(node);
        }
    
    
    }
    
    class Node {
        
        int key;
        int val;
        Node pre;
        Node next;
    
        public Node(int key, int val) {
        
            this.key = key;
            this.val = val;
        }
    }

#### 简化版两头虚拟节点代码 ####

> 添加了虚拟头尾节点后让你不用再考虑头尾为空、相同的这些问题了，非常nice

public class LRUCache {
        
    
        private Map<Integer, Node> map;
        // 虚拟头尾
        private Node first = new Node(0, 0);
        private Node last = new Node(0, 0);
        private int capacity;
    
    
        public LRUCache(int capacity) {
        
            this.capacity = capacity;
            map = new HashMap<>(capacity);
            first.next = last;
            last.pre = first;
        }
    
        private void add(Node node) {
        
            Node pre = last.pre;
            // 接节点左边的链接
            pre.next = node;
            node.pre = pre;
            // 接节点右边的链接
            node.next = last;
            last.pre = node;
        }
    
    
        private void print() {
        
            Node p = first.next;
            System.out.print("链表:");
            while (p != null && p != last) {
        
                if (p != first) {
        
                    System.out.print("->");
                }
                System.out.print(p.val);
                p = p.next;
            }
            System.out.println();
        }
    
        private Node poll() {
        
            Node poll = first.next;
            if (poll == last) {
        
                return null;
            }
            unlink(poll);
            return poll;
        }
    
    
        private void unlink(Node node) {
        
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
            node.next = node.pre = null;
        }
    
    
        public int get(int key) {
        
            Node node = map.get(key);
            // 使用过
            if (node != null) {
        
                unlink(node);
                add(node);
            }
            return node != null ? node.val : -1;
        }
    
        public void put(int key, int value) {
        
            Node node = map.get(key);
            if (node == null) {
        
                if (capacity == map.size()) {
        
                    // 需要淘汰一个
                    Node pop = poll();
                    map.remove(pop.key);
                }
                // 放入新的
                node = new Node(key, value);
                map.put(key, node);
            } else {
        
                // 覆盖
                node.val = value;
                unlink(node);
            }
            add(node);
        }
    
    
    }
    
    class Node {
        
        int key;
        int val;
        Node pre;
        Node next;
    
        public Node(int key, int val) {
        
            this.key = key;
            this.val = val;
        }
    }

[8218bf5a0b3140d6a072fb47d7cbb20a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7971ef6f7c5e4261939183445b1b08e5.png