力扣LRU缓存题解

题目链接：146. LRU 缓存机制 - 力扣（LeetCode） (leetcode-cn.com)

思路：题目要求尽量用O(1)的时间复杂度，查找用hash表，插入删除用链表

解法1

利用LinkedHashMap

class LRUCache {
    LinkedHashMap<Integer, Integer> linkedHashMap=null;
    public LRUCache(int capacity) {
        //capacity：容量
        //0.75f：负载因子
        //true：将get后的数据删除，然后重新放到链表头部
        linkedHashMap = new LinkedHashMap<>(capacity,0.75f,true){
            //当链表长度超过容量时，删除尾部的元素
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size()>capacity;
            }
        };
    }
    
    public int get(int key) {
        //get数据，如果不存在返回-1
        return linkedHashMap.getOrDefault(key,-1);
    }
    
    public void put(int key, int value) {
        linkedHashMap.put(key,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);
 */

解法2

自己构造双向链表，并结合hashmap

class LRUCache {

    //hashmap存储<key,Node<key,value>>
    private HashMap<Integer,Node> map;
    private DoubleLinkedList list;
    private int cap;
    public LRUCache(int capacity) {
        map=new HashMap<>();
        list=new DoubleLinkedList();
        cap=capacity;
    }
    
    //通过key获取Node结点的value，如果不存在返回-1
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        int value = map.get(key).value;
        //把结点重置到链表头部
        put(key,value);
        return value;
    }
    
    //如果结点存在，删除结点并重新添加到链表头部
    public void put(int key, int value) {
        Node newNode = new Node(key, value);
        if (map.containsKey(key)){
            list.delete(map.get(key));
            list.addFirst(newNode);
            map.put(key,newNode);
        }else {
            //判断链表长度是否超过容量，超过就删除最后一个结点
            if (map.size()>=cap){
                int last = list.delLast();
                map.remove(last);
            }
            //将结点放入链表头部
            list.addFirst(newNode);
            map.put(key,newNode);
        }
    }
}

//双向链表
class DoubleLinkedList{
    Node head;
    Node tail;

    //初始化链表
    public DoubleLinkedList(){
        head=new Node(0,0);
        tail=new Node(0,0);
        head.next=tail;
        tail.prev=head;
    }

    //将结点添加到链表首部
    public void addFirst(Node newNode){
        newNode.next=head.next;
        newNode.prev=head;
        head.next.prev=newNode;
        head.next=newNode;
    }

    //删除某一结点
    //返回key便于在hashmap中查找
    public int delete(Node node){
        int key=node.key;
        node.next.prev=node.prev;
        node.prev.next=node.next;
        return key;
    }

    //删除尾结点
    public int delLast(){
        if (head.next==tail)
            return -1;
        return delete(tail.prev);
    }
}

//定义Node结点，存储key，value
//指向前后结点的指针
class Node{
    int key;
    int value;
    Node prev;
    Node next;
    public Node(int key,int value){
        this.key=key;
        this.value=value;
    }
}