1.力扣146--LRU缓存
class LRUCache { class Node{ public int key; public int value; public Node pre,next; public Node(){} public Node(int key, int value){this.key = key;this.value = value;} } //双链表+哈希表实现 //哈希表并不记录插入键值对的顺序,通过双向连链表来保存他们的顺序。 public HashMap<Integer,Node> map; public int capacity; public Node tail, head; public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(); tail = new Node(); head = new Node(); head.next = tail; tail.pre = head; } public int get(int key) { //查询逻辑:如果key不在map中直接返回-1; // 如果在map中,找到该节点,在原来链表中删除该节点,然后将该节点放入链表头,返回对应的value Node temp = map.get(key); if(temp == null){ return -1; } //System.out.println(temp.value); removeToHead(temp); return temp.value; } public void put(int key, int value) { //写逻辑:如果key不在map中,将该节点放入map中,将该节点放入链表中。 Node temp = map.get(key); if(temp == null){ temp = new Node(key,value); map.put(key,temp); addToHead(temp); //如果此时哈希表个数超过我们能存放的缓存个数,删除链表最后一个节点(不常用),然后在哈希表中删除对应的节点。 if(map.size()>capacity){ //map.remove(tail.pre.key); Node node = deletTail(); map.remove(node.key); } }else{ temp.value = value; removeToHead(temp); } } private void addToHead(Node node){ //添加节点操作,先把当前节点连入,在修改前后节点。 node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; } private void delet(Node node){ node.pre.next = node.next; node.next.pre = node.pre; } private void removeToHead(Node node){ delet(node); addToHead(node); } private Node deletTail(){ Node node = tail.pre; delet(node); return node; } }
标签:11,node,temp,map,--,Node,2023.1,key,public From: https://www.cnblogs.com/lyjps/p/17045283.html