LeetCode——LRU缓存机制

NO.146 LRU缓存机制中等

思路一：双向链表+HashMap 双向链表确保插入和删除快是个 O(1) ，但是查找时链表的硬伤.

需要用一个 HashMap 去弥补链表查找上的问题，Map 的 key 存放节点的 key 、Map 的 value 存放对应的节点，形成 Map[key,node]->Node[key,value]这样的映射，从而确保了通过 key 查找节点时的速度问题。

先实现一个双向链表，要有插入/删除操作：

public class Node {
    //节点的键值
    int key, value;
    //后继和前驱
    Node next, pre;

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

public class DoubleLinkedList {
    //头尾哑节点
    Node head, tail;
    //节点个数
    int size;

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

    //表头插入节点
    public boolean addFirst(Node node) {
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
        size++;
        return true;
    }

    //删除节点(节点是从map映射中拿到的,一定存在)
    public boolean remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        size--;
        return true;
    }

    //删除表尾节点
    public Node removeLast() {
        if (head.next == tail) return null;
        Node last = tail.pre;
        remove(last);
        return last;
    }

    public int size() {
        return size;
    }
}

接下来就可以开始实现 LRUCache 了，最近访问过的节点放到链表头部，缓存已满时发生页面替换将表尾的节点删除，节点被访问之后放到表头：

public class LRUCache {
    //key 和 Node 映射
    HashMap<Integer, Node> map;
    //双向链表
    DoubleLinkedList cache;
    //缓存容量
    int capacity;

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

    public void put(int key, int value) {
        Node node = new Node(key, value);
        //如果key存在,则更新
        if (map.containsKey(key)) {
            //删除旧节点,不需要手动更新map,后面会进行覆盖
            cache.remove(map.get(key));
        } else if (cache.size == capacity) {
            //key不存在,且缓存已满
            //删除表尾节点
            Node last = cache.removeLast();
            //更新map
            map.remove(last.key);
        }
        //新节点添加到表头
        cache.addFirst(node);
        //更新map
        map.put(key, node);
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        int value = map.get(key).value;
        //使用put方法,将访问过的键值对节点放到
        put(key, value);
        return value;
    }

}

get/put 时间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.146 LRU缓存机制 中等

NO.146 LRU缓存机制中等