LeetCode-146. LRU 缓存-Java-medium

题目链接

法一（LinkedHashMap）

/**
 * 法一
 * LinkedHashMap
 * （1）定义：继承自HashMap，在HashMap基础上，通过维护一条双向链表，解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题
 * （2）数据结构：HashMap + 双向链表
 * （3）使用场景：当我们希望有顺序地去存储key-value时，就需要使用LinkedHashMap了，例如LRU缓存过期策略
 * （4）初始化参数：
 *     LinkedHashMap cache = new LinkedHashMap(capacity, 0.75f, true);
 *     capacity 初始容量
 *     loadFactor 加载因子
 *     accessOrder，默认false为插入顺序，true为访问顺序
 *     插入顺序：会按照插入顺序（put）进行排序
 *     访问顺序：会按照访问顺序（get和put）进行排序，也就是插入和访问都会将当前节点放置到尾部，尾部代表的是最近访问的数据
 * （5）removeEldestEntry()方法
 *     removeEldestEntry()方法用于检查是否删除Map中最旧的条目
 *     返回值：如果将最旧的条目从映射中删除，则返回true；如果保留该条目，则返回false。
 */
public class Solution146_1 {

    private int capacity; // LRU缓存容量
    private LinkedHashMap<Integer, Integer> cache;

    /**
     * 以正整数作为容量capacity初始化LRU缓存
     *
     * @param capacity
     */
    public Solution146_1(int capacity) {
        this.capacity = capacity;
        cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) { // 重载removeEldestEntry
                return cache.size() > capacity;
            }
        };
    }

    /**
     * 如果关键字key存在于缓存中，则返回关键字的值，否则返回-1
     *
     * @param key
     * @return
     */
    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    /**
     * 如果关键字key已经存在，则变更其数据值value; 如果不存在，则向缓存中插入该组key-value
     * 如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        cache.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

法二（双向链表 + HashMap）

/**
 * 法二（双向链表 + HashMap）
 * Java的静态内部类
 * 如果一个类要被声明为static的，只有一种情况，就是静态内部类。
 * 静态内部类实际上与普通类（即类名必须与文件名一样的顶级类）一样，只是静态内部类在某一类的内部定义了而已
 */
public class Solution146_2 {

    private int capacity; // LRU缓存容量
    private int dulSize;  // 双向链表长度
    private DulNode dulHead; // 双向链表头节点（不存数据）
    private Map<Integer, DulNode> mp = new HashMap<>(); // 建立key与双向链表节点的映射

    /**
     * 双向链表静态内部类
     */
    private static class DulNode {
        private int key, val;
        private DulNode prev, next;

        // 无参构造函数
        private DulNode() {
        }

        // 有参构造函数
        private DulNode(int key, int val) {
            this.key = key;
            this.val = val;
        }

        // 移除当前节点并返回
        private DulNode remove() {
            prev.next = next;
            next.prev = prev;
            next = null;
            prev = null;
            return this;
        }

        // 将dulNode插入到当前节点后面
        private void insert(DulNode dulNode) {
            dulNode.next = next;
            dulNode.prev = this;
            next.prev = dulNode;
            next = dulNode;
        }
    }

    /**
     * 以正整数作为容量capacity初始化LRU缓存
     *
     * @param capacity
     */
    public Solution146_2(int capacity) {
        this.capacity = capacity;
        dulHead = new DulNode(); // 初始化双向链表头节点
        dulHead.next = dulHead;
        dulHead.prev = dulHead;
    }

    /**
     * 如果关键字key存在于缓存中，则返回关键字的值，否则返回-1
     *
     * @param key
     * @return
     */
    public int get(int key) {
        DulNode dulNode = mp.get(key);
        if (dulNode == null) {
            return -1;
        }
        dulNode = dulNode.remove(); // 从双向链表中移除dulNode
        dulHead.insert(dulNode);    // 将移除的dulNode重新插入到双向链表头节点后面
        return dulNode.val;
    }

    /**
     * 如果关键字key已经存在，则变更其数据值value; 如果不存在，则向缓存中插入该组key-value
     * 如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        DulNode dulNode = mp.get(key);
        if (dulNode == null) { // key对应节点不存在，则新建一个节点
            dulNode = new DulNode(key, value);
            mp.put(key, dulNode);
            dulSize++;
        } else { // key对应节点存在，则更改该节点的值
            dulNode = dulNode.remove(); // 先移除dulNode
            dulNode.val = value;
        }
        dulHead.insert(dulNode);  // 将dulNode插入到双向链表头节点后面
        if (dulSize > capacity) { // 超出缓存容量
            DulNode dulRemoved = dulHead.prev.remove(); // 移除双向链表最后一个节点（dulHead.prev始终指向最后一个节点）
            mp.remove(dulRemoved.key);
            dulSize--;
        }
    }

}
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

本地测试

        /**
         * 146. LRU 缓存
         */
        lay.showTitle(146);
        Solution146_1 sol146_1 = new Solution146_1(2);
        sol146_1.put(1, 1); // 缓存是 {1=1}
        sol146_1.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.print(sol146_1.get(1) + " "); // 返回 1
        sol146_1.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.print(sol146_1.get(2) + " "); // 返回 -1 (未找到)
        sol146_1.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.print(sol146_1.get(1) + " "); // 返回 -1 (未找到)
        System.out.print(sol146_1.get(3) + " "); // 返回 3
        System.out.println(sol146_1.get(4) + " "); // 返回 4
        Solution146_2 sol146_2 = new Solution146_2(2);
        sol146_2.put(1, 1); // 缓存是 {1=1}
        sol146_2.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.print(sol146_2.get(1) + " "); // 返回 1
        sol146_2.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.print(sol146_2.get(2) + " "); // 返回 -1 (未找到)
        sol146_2.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.print(sol146_2.get(1) + " "); // 返回 -1 (未找到)
        System.out.print(sol146_2.get(3) + " "); // 返回 3
        System.out.println(sol146_2.get(4) + " "); // 返回 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24