题目

题目链接

https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked

解题思路

采用哈希表和双向链表的方式。其实我最开始想用队列的方式来维持，后面发现不现实，因为要动态的删除最久未使用元素。

相关代码

class LRUCache {
    Node head,tail;
    int len=0;
    Map<Integer,Node> hash = new HashMap<>();
    public LRUCache(int capacity) {
        len = capacity;
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.right = tail;
        tail.left = head;
    }
    public int get(int key) {
        Node temp = hash.get(key);
        if(temp==null) return -1;
        remove(temp);
        insert(temp);
        return temp.value;
    }
    public void put(int key, int value) {
        Node temp = hash.get(key);
        if(temp==null){
            if(hash.size()==len){
                hash.remove(tail.left.key);
                remove(tail.left);
            }
            hash.put(key,new Node(key,value));
            insert(hash.get(key));
        }   
        else{
            temp.value = value;
            remove(temp);
            insert(temp);
        } 
    }
    public void remove(Node p){
        p.left.right = p.right;
        p.right.left = p.left;
    }
    public void insert(Node p){
        p.right = head.right;
        head.right.left = p;
        head.right = p;
        p.left = head;
    }
}
class Node {
    int key,value;
    Node left,right;
    public Node(int key,int value){
        this.key = key;
        this.value = value;
    }
}