146. LRU 缓存
使用哈希表和双向链表解决(也可以LinkedHashMap)
用于操作链表的方法为removeNode, addToHead.
在put中:
如果不存在key,则为添加, ++size, 需要判断容量;
容量超过,则尾删, --size;
容量没超过, 则不删;
如果存在key, 则为修改, 不需要判断容量;
以上两步均为操作,因此都得addToHead.
class Node{public int key, val;public Node prev;public Node next;public Node(int a, int b){this.key = a;this.val = b;this.prev = null;this.next = null;}public Node(){this.key = 0;this.val = 0;this.prev = null;this.next = null;}
}
class LRUCache {private Node head;private Node tail;private Map<Integer, Node>map = new HashMap<>();private int capacity;private int size;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new Node();tail = new Node();head.next = tail;tail.prev = head;}public int get(int key) {if(!map.containsKey(key)){return -1;}Node temp = map.get(key);removeNode(temp);addToHead(temp);return temp.val;}public void put(int key, int value) {Node node = map.get(key);if(node == null){Node newNode = new Node(key, value);map.put(key, newNode);addToHead(newNode);++size;if(size > capacity){Node tail1 = tail.prev;map.remove(tail1.key);removeNode(tail1);--size;}}else {node.val = value;removeNode(node);addToHead(node);}}public void removeNode(Node node){node.next.prev = node.prev;node.prev.next = node.next;}public void addToHead(Node node){node.next = head.next;node.prev = head;head.next = node;node.next.prev = node;}
}先前我在实现put操作时使用了containsKey,这使得我原来的代码时间消耗很高
