题解 | #设计LRU缓存结构#

手写双链表，哈希表加双链表实现LRU

package TEST;

import java.util.*;

public class Solu {
//手写双向链表节点
class DlinkNode {
int key;
int val;
DlinkNode pre;//声明不用初始化
DlinkNode next;

    public DlinkNode(int key, int val) {
        this.key = key;
        this.val = val;
    }

    public DlinkNode() {
    }
}

//LRUCache的类结构以及内部方法
class LRUCache {
    Map<Integer, DlinkNode> map;
    DlinkNode head;
    DlinkNode tail;
    int size;
    int capacity;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        map = new HashMap<>();
        //链表的结构开始节点首尾相连
        head = new DlinkNode();
        tail = new DlinkNode();
        head.next = tail;
        tail.pre = head;
    }


    public void set(int key, int value) {
        DlinkNode node = map.get(key);
        if (node == null) {
            DlinkNode newNode = new DlinkNode(key, value);
            addToHead(newNode);
            map.put(key, newNode);
            size++;
            if(size>capacity){
                map.remove(tail.pre.key);//只能移除key值 不能移除value？
                removeNode(tail.pre);
                size--;
            }
        } else {
            node.val = value;
            //删除 再插入至头部 两个O（1）完成移动至头部的操作
            removeNode(node);
            addToHead(node);
        }
    }

    private void removeNode(DlinkNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addToHead(DlinkNode newNode) {
        newNode.pre = head;
        newNode.next = head.next;
        head.next.pre = newNode;
        head.next = newNode;
    }

    public int getV(int key) {
        DlinkNode node = map.get(key);
        if(node == null){
            return -1;
        }
        else {
            removeNode(node);
            addToHead(node);
            return node.val;
        }
    }


}


/**
 * lru design
 *
 * @param operators int整型二维数组 the ops
 * @param k         int整型 the k
 * @return int整型一维数组
 */
public int[] LRU(int[][] operators, int k) {
    if (operators == null || operators.length == 0) {
        return null;
    }
    LRUCache Cache = new LRUCache(k);
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < operators.length; i++) {
        if (operators[i][0] == 1) {
            Cache.set(operators[i][1], operators[i][2]);
        } else if (operators[i][0] == 2) {
            int res = Cache.getV(operators[i][1]);
            list.add(res);
        }
    }
    int[] ans = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        ans[i] = list.get(i);
    }
    return ans;

}

}
/*
class Te{
public static void main(String[] args) {
Solu solu = new Solu();
int[][] opre = new int[][]{{1,1,1},{1,1,2},{2,1}};
int[] lru = solu.LRU(opre, 3);
System.out.println(Arrays.toString(lru));
}
}*/