这个博客是为了十年前找工作时候创建的，用来记录自己的积累，没想到，一晃十年，我又回到了这里，想Mark下，时光弹指一瞬，令人唏嘘。
记录一道代码题吧。
力扣
Problem: 146. LRU 缓存
思路
解题方法
复杂度
Code
思路
使用一个Map来存储数据，使用双端链表来做LRU元素排序，新访问的元素插入表尾，最早的元素就被排序到表头了。
解题方法
注意元素为0个的判定和处理。map里要保存在双端链表的位置，使用一个node结构体都保存了
复杂度
时间复杂度:
get是o(1), put也是o(1)
空间复杂度:
o(n)
class LRUCache {private class Node {int key;int value;Node pre;Node next;Node(int k, int v) {key = k;value = v;pre = next = null;}Node() {}}HashMap<Integer, Node> cache;int capacity;int size;Node head;public LRUCache(int capacity) {this.capacity = capacity;size = 0;head = new Node();head.next = head.pre = head;cache = new HashMap<Integer, Node>();}public int get(int key) {Node data = cache.get(key);if(data != null) {Node pre = data.pre;Node next = data.next;pre.next = data.next;next.pre = data.pre;pre = head.pre;pre.next = data;data.pre = pre;data.next = head;head.pre = data;return data.value;} else {return -1;}}public void put(int key, int value) {Node n = cache.get(key);if(n != null) {n.value = value;n.pre.next = n.next;n.next.pre = n.pre;Node pre = head.pre;pre.next = n;n.pre = pre;n.next = head;head.pre = n;} else {Node newNode = new Node(key, value);Node pre = head.pre;head.pre = newNode;newNode.next = head;if(pre != null) {pre.next = newNode;newNode.pre = pre;} else {head.next = newNode;newNode.pre = head;}cache.put(key, newNode);size++;if(size > capacity) {Node delNode = head.next;Node next = delNode.next;head.next = next;next.pre = head;cache.remove(delNode.key);size--;}}}
}/*** 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);*/作者：neomcgo
链接：https://leetcode.cn/problems/lru-cache/solutions/2334297/lruhuan-cun-by-neomcgo-3ozo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
