LeetCode: 146. LRU Cache

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

146. LRU Cache

LeetCode - LRU Cache

使用双向链表实现时，使用两个"空节点" head 和 tail，可以有效减少空值判断，真是精巧。想起来上大学时，老师讲课提到这么一句。没想到竟然是如此实现。

LinkedHashMap 的实现也有不少的秘密可以探索。

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:

Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 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
 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
/**
 * Runtime: 14 ms, faster than 90.57% of Java online submissions for LRU Cache.
 *
 * Memory Usage: 50.8 MB, less than 96.93% of Java online submissions for LRU Cache.
 *
 * Copy from: https://leetcode-cn.com/problems/lru-cache/solution/lru-huan-cun-ji-zhi-by-leetcode/[LRU 缓存机制 - LRU缓存机制 - 力扣（LeetCode）]
 */
class LRUCache {
    private Map<Integer, DLinkedNode> data;
    private int capacity;
    private int size;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        this.data = new HashMap<>();
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();

        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public int get(int key) {
        DLinkedNode node = data.get(key);
        if (Objects.isNull(node)) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = data.get(key);
        if (Objects.isNull(node)) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            data.put(key, newNode);
            addNode(newNode);
            ++size;
            if (size > capacity) {
                DLinkedNode tail = popTail();
                data.remove(tail.key);
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void addNode(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addNode(node);
    }

    private DLinkedNode popTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

    private class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }
}

/**
 * Runtime: 22 ms, faster than 43.05% of Java online submissions for LRU Cache.
 *
 * Memory Usage: 58 MB, less than 51.53% of Java online submissions for LRU Cache.
 */
class LRUCacheLinkedHashMap {
    private LinkedHashMap<Integer, Integer> data;

    public LRUCacheLinkedHashMap(int capacity) {
        data = new LinkedHashMap<Integer, Integer>(capacity, 0.75F, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return this.size() > capacity;
            }
        };
    }

    public int get(int key) {
        return data.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        data.put(key, value);
    }
}

private void test() {
    LRUCache solution = new LRUCache(2);
    solution.put(1, 1);
    solution.put(2, 2);
    int r1 = solution.get(1);
    System.out.println((r1 == 1) + " : " + r1);
    solution.put(3, 3);
    int r2 = solution.get(2);
    System.out.println((r2 == -1) + " : " + r2);
    solution.put(4, 4);
    int r3 = solution.get(1);
    System.out.println((r3 == -1) + " : " + r3);
    int r4 = solution.get(3);
    System.out.println((r4 == 3) + " : " + r4);
    int r5 = solution.get(4);
    System.out.println((r5 == 4) + " : " + r5);
}