526互联

LRU 力扣 146 https://leetcode.cn/problems/lru-cache/

发布时间 2023-07-07 10:27:39作者: 故里oc

一道经典题目，用双向链表去做能够满足O1的复杂度

核心代码如下

class LRUCache {
    MyLinkedList myLinkedList;
    int size;
    int capacity;
    HashMap<Integer, MyNode> map;
    public LRUCache(int capacity) {
​
​
        myLinkedList=new MyLinkedList();
        this.capacity=capacity;
        size=0;
        map=new HashMap<>();
    }
​
    public int get(int key) {
​
        if (!map.containsKey(key)){
            return -1;
        }
    //    拿出来 放到顶部
​
        MyNode current = map.get(key);
​
        myLinkedList.deleteAndAddFirst(current);
​
        return current.val;
    }
​
    public void put(int key, int value) {
​
        if (map.containsKey(key)){
        //    老人了
​
            MyNode current = map.get(key);
            current.val=value;
            myLinkedList.deleteAndAddFirst(current);
            map.put(key,current);
        }else {
​
            if (size<capacity){
            //    直接放进来就行
                MyNode temp = new MyNode(key, value);
                myLinkedList.add(temp);
                map.put(key,temp);
                size++;
            }else {
            //    踢人了
​
                MyNode myNode = myLinkedList.removeLast();
                map.remove(myNode.key);
​
            //    再放进
                MyNode temp = new MyNode(key, value);
                myLinkedList.add(temp);
                map.put(key,temp);
                
​
            }
​
​
​
​
​
​
        }
​
​
​
​
    }
}
class MyLinkedList{
    MyNode head;
    MyNode tail;
​
    public MyLinkedList() {
        head=new MyNode(-1,-1);
        tail=new MyNode(-1,-1);
        head.next=tail;
        tail.pre=head;
    }
​
    /**
     * 把之前的放到新的位置
     * @param current
     */
    public void deleteAndAddFirst(MyNode current){
​
        //去除之前的位置
        MyNode next = current.next;
        MyNode pre = current.pre;
​
        pre.next=next;
        next.pre=pre;
        add(current);
​
    }
​
    public void add(MyNode current){
​
        MyNode old = head.next;
        current.next=old;
        head.next=current;
        old.pre=current;
        current.pre=head;
​
​
    }
    public MyNode  removeLast(){
​
        MyNode last = tail.pre;
        MyNode pre= last.pre;
​
        pre.next=tail;
        tail.pre=pre;
        return last;
    }
}
​
class MyNode{
​
    Integer key;
    Integer val;
    MyNode next;
    MyNode pre;
​
    public MyNode(Integer key, Integer val) {
        this.key = key;
        this.val = val;
    }
}

题解