146. LRU cache

---

前言

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构.
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 .
void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value .如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字.
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行.

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lru-cache
著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处.

解题思路

实现的方法
0)构造方法, cache大小

1. void put(key, value)
2. void update(key, value)
3. V get(key)
   要求时间复杂度0(1),It avoids traversalO(N),and an ordered tableO(N*logN)

Don't panic when designing data structures,It must all be possible with simple data structures,
Just look at how this simple data structure is combined,including difficultLRU, LFU都一样.

双向链表+哈希表实现
Hash表里 A
value: Key对应的节点Node (A, 3),
A doubly linked list has nodeslast, next指针
Use a doubly linked list to indicate who is the most recent operator,who is operating from a distance
The closer to the tail of the doubly linked list, the closer,The closer to the head of the doubly linked list, the further away
A doubly linked list has a head pointer,Remember a tail pointer,It is very convenient to hang a data directly on the tail.

手动实现双向链表.
1)新加一个Node节点,Hanging at the end of the doubly linked list
2)已知一个NodeMust be on a doubly linked list,把NodeHang it on the tail after the front and rear environments are reconnected
3)Delete the head node in the doubly linked list

代码

class LRUCache {
    
    private MyCache<Integer,Integer> cache;
    public LRUCache(int capacity) {
    
		cache = new MyCache<>(capacity);
	}

	public int get(int key) {
    
		Integer ans = cache.get(key);
		return ans == null ? -1 : ans;
	}

	public void put(int key, int value) {
    
		cache.set(key, value);
	}

	public static class Node<K, V> {
    
		public K key;
		public V value;
		public Node<K, V> last;
		public Node<K, V> next;

		public Node(K key, V value) {
    
			this.key = key;
			this.value = value;
		}
	}

	public static class NodeDoubleLinkedList<K, V> {
    
		private Node<K, V> head;
		private Node<K, V> tail;

		public NodeDoubleLinkedList() {
    
			head = null;
			tail = null;
		}

		public void addNode(Node<K, V> newNode) {
    
			if (newNode == null) {
    
				return;
			}
			if (head == null) {
    
				head = newNode;
				tail = newNode;
			} else {
    
				tail.next = newNode;
				newNode.last = tail;
				tail = newNode;
			}
		}

		public void moveNodeToTail(Node<K, V> node) {
    
			if (tail == node) {
    
				return;
			}
			// node 不是尾巴
			if (head == node) {
    
				head = node.next;
				head.last = null;
			} else {
    
				node.last.next = node.next;
				node.next.last = node.last;
			}
			node.last = tail;
			node.next = null;
			tail.next = node;
			tail = node;
		}

		public Node<K, V> removeHead() {
    
			if (head == null) {
    
				return null;
			}
			Node<K, V> res = head;
			if (head == tail) {
     // 链表中只有一个节点的时候
				head = null;
				tail = null;
			} else {
    
				head = res.next;
				res.next = null;
				head.last = null;
			}
			return res;
		}

	}

	public static class MyCache<K, V> {
    
		private HashMap<K, Node<K, V>> keyNodeMap;
		private NodeDoubleLinkedList<K, V> nodeList;
		private final int capacity;

		public MyCache(int cap) {
    
			if (cap < 1) {
    
				throw new RuntimeException("should be more than 0.");
			}
			keyNodeMap = new HashMap<K, Node<K, V>>();
			nodeList = new NodeDoubleLinkedList<K, V>();
			capacity = cap;
		}

		public V get(K key) {
    
			if (keyNodeMap.containsKey(key)) {
    
				Node<K, V> res = keyNodeMap.get(key);
				nodeList.moveNodeToTail(res);
				return res.value;
			}
			return null;
		}

		public void set(K key, V value) {
    
			if (keyNodeMap.containsKey(key)) {
    
				Node<K, V> node = keyNodeMap.get(key);
				node.value = value;
				nodeList.moveNodeToTail(node);
			} else {
    
				if (keyNodeMap.size() == capacity) {
    
					removeMostUnusedCache();
				}
				Node<K, V> newNode = new Node<K, V>(key, value);
				keyNodeMap.put(key, newNode);
				nodeList.addNode(newNode);
			}
		}

		private void removeMostUnusedCache() {
    
			Node<K, V> removeNode = nodeList.removeHead();
			keyNodeMap.remove(removeNode.key);
		}

	}
}