请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

分析

关注：

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

以O(1)的时间复杂度进行get和put,数据结构需采用双向链表+Map

自定义链表

初始化
image.png

  • 易错点1：链表的引用关系,移除了链表的节点后，引用关系发生改变，map需要重新put新的引用节点

  • [x] 易错点2：链表的引用关系,移除了链表的节点后，引用关系发生改变，map需要重新put新的引用节点

    1. class LRUCache {
    3.       DLink dLink;
    4.       Map<Integer,Node> map;
    5.       int cap;
    7.       public LRUCache(int capacity) {
    8.           dLink  = new DLink();
    9.           map = new HashMap<>();
    10.           this.cap = capacity;
    11.       }
    13.       public int get(int key) {
    14.           if (map.containsKey(key)){
    15.               int val = map.get(key).val;
    16.               put(key,val);
    17.               return val;
    18.           }
    19.           return -1;
    20.       }
    22.       public void put(int key, int value) {
    23.           Node node = new Node(key,value);
    24.           if (map.containsKey(key)){
    25.               dLink.remove(map.get(key));
    26.               dLink.addHead(node);
    27.               map.put(key,node); //易错点1
    28.           }else {
    29.               if (map.size() == cap){
    30.                   int oldKey = dLink.remove(dLink.tail.pre);
    31.                   map.remove(oldKey);
    32.               }
    33.               map.put(key,node); //易错点2
    34.               dLink.addHead(node);
    35.           }
    36.       }
    37.   class Node {
    38.       int key;
    39.       int val;
    40.       Node next = null;
    41.       Node pre = null;
    42.       public Node(int key,int val) {
    43.           this.key = key;
    44.           this.val = val;
    45.       }
    46.   }
    48.   class DLink {
    50.       Node head;
    51.       Node tail;
    53.       public DLink() {
    54.           this.head = new Node(-1,-1);
    55.           this.tail = new Node(-1,-1);
    56.           head.next = tail;
    57.           tail.pre = head;
    58.       }
    60.       public void addHead(Node node){
    61.           node.next = head.next;
    62.           node.pre = head;
    63.           head.next.pre = node;
    64.           head.next = node;
    65.       }
    67.       public int remove(Node node){
    68.           node.pre.next = node.next;
    69.           node.next.pre = node.pre;
    70.           node.pre = null;
    71.           node.next = null;
    72.           return node.key;
    73.       }
    74.   }
    75. }

    易错点图示

    image.png