LC.P146[LRU缓存]

LC.P146[LRU缓存]

方法一：手写LRU

class LRUCache {

    private static class Node {
        int key, value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    int capacity;
    Node dummy = new Node(0, 0); // 哨兵节点
    Map<Integer, Node> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node != null ? node.value : -1;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null) {
            node.value = value;
            return;
        }
        node = new Node(key, value);
        map.put(key, node);
        addFirst(node);
        if (map.size() > capacity) {
            Node backNode = dummy.prev;
            map.remove(backNode.key);
            remove(backNode);
        }
    }

    private Node getNode(int key) {
        if (!map.containsKey(key)) return null;
        Node node = map.get(key);
        remove(node);
        addFirst(node);
        return node;
    }

    private void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    private void addFirst(Node x) {
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
}

/**
 * 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);
 */

方法二：手写LRU

class LRUCache {

    private Map<Integer, Node> map;
    private DoubleLinkedList cache;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.cache = new DoubleLinkedList();
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        makeRecently(key); // 将该key提升为最近使用的
        return map.get(key).value;
    }
    
    public void put(int key, int value) {
        // 情况1：原本已经有该key
        if (map.containsKey(key)) {
            deleteKey(key);
            addRecently(key, value);
            return;
        }

        // 情况2：原本没有该key
        if (cache.size == capacity) {
            // 若缓存容量满了，需删除最近最少使用的元素
            removeLeastRecently();
        }
        // 添加元素
        addRecently(key, value);
    }

    // 将key提升为最近使用
    private void makeRecently(int key) {
        Node node = map.get(key);
        cache.remove(node);
        cache.addLast(node);
    }

    // 删除指定key
    private void deleteKey(int key) {
        Node node = map.get(key);
        cache.remove(node);
        map.remove(key);
    }

    // 添加最近使用的元素
    private void addRecently(int key, int value) {
        Node x = new Node(key, value);
        cache.addLast(x);
        map.put(key, x);
    }

    private void removeLeastRecently() {
        Node node = cache.removeFirst();
        map.remove(node.key);
    }

    private static class DoubleLinkedList {
        // 头结点
        private Node head;
        // 尾结点
        private Node tail;
        // 元素个数
        private int size;

        public DoubleLinkedList() {
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }

        // 在尾部插入节点
        private void addLast(Node x) {
            x.prev = tail.prev;
            x.next = tail;
            tail.prev.next = x;
            tail.prev = x;
            ++size;
        }

        // 删除目标节点
        private void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
            --size;
        }

        // 删除链表中的第一个节点，并返回该节点
        private Node removeFirst() {
            if (head.next == tail) return null;
            Node x = head.next;
            remove(x);
            return x;
        }

        // 返回链表长度
        private int size() {
            return size;
        }
    }

    private static class Node {
        private int key;
        private int value;
        private Node next;
        private Node prev;

        public Node (int key, int value) {
            this.key = key;
            this.value = 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);
 */

方法三：继承LinkedHashMap

class LRUCache extends LinkedHashMap<Integer, Integer> {

    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true); // 按读取顺序排序设为 true
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }

    // 重写此方法实现LRU策略
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

/**
 * 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);
 */