题目链接

LRU 缓存

题目描述

注意点

• 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字
• 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行

解答思路

• 如果想以O(1)的速度进行get，则需要将对应的key、value存到哈希表中
• 如果想以O(1)的速度进行put，又因为插入的时候可能由于空间已满需要将最久未使用的关键字，元素始终都在进行移动，所以需要使用链表来存储节点，为了方便找到链表中的节点和做移动操作，所以使用双端链表来进行存储
• 如果使用map存储key、value，链表中每个节点存储key、value，则在get某个节点需要将其移动到链表头部时查找该节点需要花费O(n)的时间，不满足题意，所以应该map存储的key为对应关键字的key，而存储的value应该是该key对应的链表节点
• 所以最终使用哈希表+双端链表解决本题，其中哈希表中key对应put中的key，value为一个双端链表中的节点，维护双端链表的头尾节点和节点关系

代码

class LRUCache {
    int capacity;
    Map<Integer, Node> map;
    Node root;
    Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        root = new Node();
        tail = new Node();
        root.next = tail;
        tail.prev = root;
    }
    
    public int get(int key) {
        if (map.get(key) == null) {
            return -1;
        }
        Node node = map.get(key);
        // 删除链表原位置并移动至链表头部
        deleteNode(node);
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        // 如果该节点已添加过，重新赋值，删除链表原位置并移动至链表头部即可
        if (map.get(key) != null) {
            Node oldNode = map.get(key);
            oldNode.value = value;
            deleteNode(oldNode);
            moveToHead(oldNode);
            return;
        }
        // 如果该节点未添加过，需要添加到map中并移动至链表头部
        Node node = new Node(key, value);
        map.put(key, node);
        moveToHead(node);
        // 超出容量，逐出最久未使用的关键字（尾部节点）
        if (map.size() > capacity) {
            Node lastNode = tail.prev;
            deleteNode(lastNode);
            map.remove(lastNode.key);
        }
    }

    public void deleteNode(Node node) {
        Node prevNode = node.prev;
        Node nextNode = node.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    public void moveToHead(Node node) {
        Node nextNode = root.next;
        root.next = node;
        node.prev = root;
        node.next = nextNode;
        nextNode.prev = node;
    }
}

class Node {
    int key;
    int value;
    Node prev;
    Node next;
    public Node() {}
    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);
 */

关键点

• map中存储的value为key对应链表中的节点
• 如果能成功get到值，则需要将该节点移动到链表的头部，移动至头部前要先删除链表中该节点的老位置
• 在put时，有以下两种情况
  • 如果此时map中已经有相应key，对应节点为node，则对node中value重新赋值，并将node移动至头部即可
  • 如果此时map中没有相应key，则需要创建一个新节点newNode并将newNode移动至链表头部，除此之外，如果此时已超出容量，还需要删除尾部的节点
• 在增加和删除链表节点时同时也要对map中的相应值进行更新
• 注意在对链表进行操作时头尾节点可能发生改变，所以最好先用node存储当前的头尾节点，再对node进行操作