NC93 & LeetCode 146. LRU 缓存 Java注释版

NC93 & LeetCode 146. LRU 缓存 Java注释版

NC93 & LeetCode 146. LRU 缓存

import java.util.*;
 
public class Solution {
    
    public int[] LRU (int[][] operators, int k) {
        // write code here
        List list = new ArrayList<>();
        LRUCache lru = new LRUCache(k);
        for (int[] p : operators) {
            int op = p[0];
            if (op == 1) {
                lru.put(p[1], p[2]);
            } else if (op == 2) {
                list.add(lru.get(p[1]));
            }
        }
        int n = list.size();
        int[] ans=  new int[n];
        for (int i = 0; i < n; i++) ans[i] = list.get(i);
        return ans;
    }
}
 
class LRUCache {
    //定义双向链表节点
    class Node {
        int k, v;
        Node l, r;
        Node(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }
    int n; //储存缓存容量值
    Node head, tail; //设置虚拟的头尾节点
    Map map; //储存节点的key以及节点
    public LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.r = tail;
        tail.l = head;
    }
     
    int get(int key) {
        Node node = null;
        //在找到对应节点则将其挪到链表头部
        if (map.containsKey(key)) {
            node = map.get(key);
            refresh(node);
            return node.v;
        }
        return -1;
    }
     
    void put(int key, int val) {
        Node node = null;
        //如果节点在map中，说明它也在链表中。因此更新其值，并将其挪到双向链表头部
        if (map.containsKey(key)) {
            node = map.get(key);
            node.v = val;
            refresh(node); //将node挪到双向链表头部
            return;
        }
        //如节点不在map中，则需要新建节点储存当前的key&val
        if (map.size() == n) {
            //储存空间不足，执行LRU算法。（在链表以及map中同时）删除双向链表尾部节点（最久未被访问节点）
            Node last = tail.l;
            map.remove(last.k);
            delete(last);
        }
        //将新节点放在链表头部
        node = new Node(key, val);
        map.put(key, node);
        refresh(node);
       
    }
     
    //将当前访问的node挪到双向链表头部
    void refresh(Node node) {
        delete(node);
        node.r = head.r;
        node.l = head;
        head.r.l = node;
        head.r = node;
    }
     
    //删除目标节点
    void delete(Node node) {
        //若目标节点的左指针为空，则说明它不在双向链表中
        if (node.l != null) {
            Node left = node.l;
            Node right = node.r;
            left.r = right;
            right.l = left;
        }
        
    }
     
}