禅城网站建设代理,微信网站的结构,免费可以看的软件大全下载,南通网站建设规划书分析
维护一个双向链表保存缓存中的元素。 如果元素超过容量阈值#xff0c;则删除最久未使用的元素。为了实现这个功能#xff0c;将get(), put()方法获取的元素添加到链表首部。 为了在O(1)时间复杂度执行get()方法#xff0c;再新建一个映射表#xff0c;缓存key与链表…分析
维护一个双向链表保存缓存中的元素。 如果元素超过容量阈值则删除最久未使用的元素。为了实现这个功能将get(), put()方法获取的元素添加到链表首部。 为了在O(1)时间复杂度执行get()方法再新建一个映射表缓存key与链表节点。
源码
class LRUCache {private int size;private int capacity;private MapInteger, Node cache new HashMap();private Node head;private Node tail;public LRUCache(int capacity) {this.capacity capacity;this.size 0;this.head new Node();this.tail new Node();this.head.next this.tail;this.tail.prev this.head;}public int get(int key) {Node node cache.get(key);if (node null) {return -1;}moveToHead(node);return node.value;}public void put(int key, int value) {Node node cache.get(key);if (node null) {node new Node(key, value);cache.put(key, node);addToHead(node);size;if (size capacity) {Node tail removeTail();cache.remove(tail.key);size--;}}node.value value;moveToHead(node);}private void addToHead(Node node) {node.prev head;node.next head.next;head.next.prev node;head.next node;}private void removeNode(Node node) {node.prev.next node.next;node.next.prev node.prev;}private void moveToHead(Node node) {removeNode(node);addToHead(node);}private Node removeTail() {Node res tail.prev;removeNode(res);return res;}class Node {int key;int value;Node prev;Node next;public Node(int key, int value) {this.key key;this.value value;}public Node() {}}
}
