牛客NC93 设计LRU缓存结构【hard 链表，Map Java】

题目

在这里插入图片描述

题目链接：
https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84

思路

	双向链表+map最新的数据放头结点，尾节点放最老的数据，没次移除尾巴节点本地考察链表的新增，删除，移动节点

参考答案Java

import java.util.*;public class Solution {Map<Integer, Node> cache = new HashMap<>();Node start, end;int cap = 0;public Solution(int capacity) {// write code herecap = capacity;}public int get(int key) {//key对应节点移动到头部，成为头节点if (!cache.containsKey(key)) return -1;Node cur = cache.get(key);int v = cur.data;Node next = cur.next;Node prev = cur.prev;if (next != null && prev != null) { //cur 要变成头结点next.prev = prev;prev.next = next;if (next.next == null) { //这里似乎可以不要end = next;}cur.next = start;start.prev = cur;start = cur;} else if (next != null) { //说明cur是头结点，不管了} else if (prev != null) { //自己是尾结点prev.next = null; //自己的prev要成为尾巴，prev.next设置为nullcur.next = start;start.prev = cur;start = cur;end = prev; //尾巴修改为自己的前一个节点}return v;}public void set(int key, int value) {if (cache.containsKey(key)) {cache.get(key).data = value;cache.put(key, cache.get(key));get(key); //使用一次，移动到头部} else {Node node = new Node(key, value);if (cap == 1) { //容量为1时特殊处理start = end = node;cache.clear();cache.put(key, node);return;}int size = cache.size();if (start == null) {start = node;end = node;cache.put(key, node);} else if (size < cap) { //不需要移除尾节点，直接修改头部node.next = start;start.prev = node;start = node;cache.put(key, node);} else {
//                        System.out.println();
//                        System.out.println(key+" == "+value);
//                        System.out.println();Node last = end;Node lastprev = last.prev;end = lastprev; //设置新的尾节点cache.remove(last.key);end.next = null;last = null;node.next = start;start.prev = node;start = node; //设置新的头结点cache.put(key, node);}//show(start);}}static class Node {int key;int data;Node prev;Node next;public Node(int k, int d) {key = k;data = d;}}public void show(Node root) { //帮助打印的，本答案可以不需要System.out.println("");Node t = root;Set<Integer> s = new HashSet<>();while (t != null) {System.out.print(t.key + "=>" + t.data + "   ");t = t.next;//if(s.contains(t.data)) break;}System.out.println("");}}/*** Your Solution object will be instantiated and called as such:* Solution solution = new Solution(capacity);* int output = solution.get(key);* solution.set(key,value);*/