请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

LRU 缓存

2023-07-13

题目链接

LRU 缓存

题目描述


注意点

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

解答思路

  • 如果想以O(1)的速度进行get,则需要将对应的key、value存到map中
  • 如果想以O(1)的速度进行put,又因为插入的时候可能由于空间已满需要将最久未使用的关键字,元素始终都在进行移动,所以需要使用链表来存储节点
  • 如果使用map存储key、value,链表中每个节点存储key、value,则在get某个节点需要将其移动到链表头部时查找该节点需要花费O(n)的时间,不满足题意,所以应该map存储的key为对应关键字的key,而存储的value应该是该key对应的链表节点

代码

class LRUCache {
    class DoublyLinkedList {
        int key;
        int value;
        DoublyLinkedList prev;
        DoublyLinkedList next;
        DoublyLinkedList() {}
        DoublyLinkedList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    int size;
    DoublyLinkedList head;
    DoublyLinkedList tail;
    Map<Integer, DoublyLinkedList> map;

    public LRUCache(int capacity) {
        size = capacity;
        map = new HashMap<>(capacity);
        head = new DoublyLinkedList();
        tail = new DoublyLinkedList();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DoublyLinkedList node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 将该节点移动到链表头部
        removeNode(node);
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DoublyLinkedList node = new DoublyLinkedList(key, value);
        // key在链表中已存在,只更新了value值,则直接对map进行更新即可,还要将新节点移动到链表头部
        if (map.containsKey(key)) {
            DoublyLinkedList oldNode = map.get(key);
            removeNode(oldNode);
            map.put(key, node);
            moveToHead(node);
            return;
        }
        // key在链表中不存在,且链表还有多余空间,则只需要将新节点插到链表头部
        if (map.size() < size) {
            moveToHead(node);
            map.put(key, node);
        } else {
            // key在链表中不存在,且链表已满,则需要删除链表尾,同时将新节点插到链表头部
            map.remove(tail.prev.key);
            removeNode(tail.prev);
            moveToHead(node);
            map.put(key, node);
        }
    }

    public void moveToHead(DoublyLinkedList node) {
        DoublyLinkedList tmp = head.next;
        head.next = node;
        node.prev = head;
        node.next = tmp;
        tmp.prev = node;
    }

    public void removeNode(DoublyLinkedList node) {
        DoublyLinkedList prevNode = node.prev;
        DoublyLinkedList nextNode = node.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }
}

关键点

  • map中存储的value为key对应的链表中的节点
  • 如果能成功get到值,则需要将该节点移动到链表的头部,移动时,还要删除链表中老位置的该节点
  • 在put时,如果此时链表和map中已经有该关键字,只是更新其value值,则需要更新其在链表中的节点值,同时将该节点移动到链表同步;如果没有该关键字但是链表空间足够,则只需要建一个新节点插到链表头部即可;如果没有该关键字且链表空间已满,则需要将尾部节点删掉,再将新节点插入到头部
  • 在增加和删除链表节点时同时也要对map中的相应值进行更新

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部