用dw做音乐网站模板,策划公司收费明细,东莞市建设工程质量监督网,wordpress 随机图片题目
请设计实现一个最近最少使用#xff08;Least Recently Used#xff0c;LRU#xff09;缓存#xff0c;要求如下两个操作的时间复杂度都是O#xff08;1#xff09;。
get#xff08;key#xff09;#xff1a;如果缓存中存在键key#xff0c;则返回它对应的值…题目
请设计实现一个最近最少使用Least Recently UsedLRU缓存要求如下两个操作的时间复杂度都是O1。
getkey如果缓存中存在键key则返回它对应的值否则返回-1。putkeyvalue如果缓存中之前包含键key则它的值设为value否则添加键key及对应的值value。在添加一个键时如果缓存容量已经满了则在添加新键之前删除最近最少使用的键缓存中最长时间没有被使用过的元素。
分析
哈希表HashMap的get操作和put操作的时间复杂度都是O1但普通的哈希表无法找出最近最少使用的键因此需要在哈希表的基础上进行改进。
由于需要知道缓存中最近最少使用的元素因此可以把存入的元素按照访问的先后顺序存入链表中。每次访问一个元素无论是通过get操作还是通过put操作该元素都被移到链表的尾部。这样位于链表头部的元素就是最近最少使用的。
下面考虑如何实现把一个节点移到链表的尾部。这实际上包含两个步骤首先要把节点从原来的位置删除然后把它添加到链表的尾部。需要注意的是在链表中删除一个节点实际上是把它的前一个节点的next指针指向它的下一个节点。如果这个链表是单向链表那么找到一个节点的前一个节点需要从链表的头节点开始顺序扫描每个节点也就需要On的时间。
为了快速找到一个节点的前一个节点从而实现用O1的时间删除一个节点可以用双向链表来存储缓存中的元素。在双向链表中查找一个节点的前一个节点只需要顺着prev指针向前走一步时间复杂度为O1。
因此设计最近最少使用缓存需要结合哈希表和双向链表的特点。哈希表的键就是缓存的键哈希表的值为双向链表中的节点每个节点都是一组键与值的数对。
解
public class Test {public static void main(String[] args) {LRUCache lruCache new LRUCache(4);lruCache.put(1,1);lruCache.put(2,2);lruCache.put(3,3);lruCache.put(4,4);ListNode node1 lruCache.head;while (node1 ! null){System.out.println(node1.value);node1 node1.next;}System.out.println(-------------------------);lruCache.get(2);ListNode node2 lruCache.head;while (node2 ! null){System.out.println(node2.value);node2 node2.next;}System.out.println(-------------------------);lruCache.put(1,8);ListNode node3 lruCache.head;while (node3 ! null){System.out.println(node3.value);node3 node3.next;}System.out.println(-------------------------);lruCache.put(5,5);ListNode node4 lruCache.head;while (node4 ! null){System.out.println(node4.value);node4 node4.next;}}static class ListNode{public int key;public int value;public ListNode next;public ListNode prev;public ListNode(int k,int v){key k;value v;}}static class LRUCache{private ListNode head;private ListNode tail;private MapInteger,ListNode map;int capacity;public LRUCache(int cap){map new HashMap();head new ListNode(-1,-1);tail new ListNode(-1,-1);head.next tail;tail.prev head;capacity cap;}public int get(int key){ListNode node map.get(key);if (node null){return -1;}moveToTail(node,node.value);return node.value;}public void put(int key,int value){if (map.containsKey(key)){moveToTail(map.get(key),value);}else {if (map.size() capacity){ListNode toBeDeleted head.next;deleteNode(toBeDeleted);map.remove(toBeDeleted.key);}ListNode node new ListNode(key,value);intsertToTail(node);map.put(key,node);}}private void moveToTail(ListNode node,int newValue){deleteNode(node);node.value newValue;intsertToTail(node);}private void deleteNode(ListNode node){node.prev.next node.next;node.next.prev node.prev;}private void intsertToTail(ListNode node){tail.prev.next node;node.prev tail.prev;node.next tail;tail.prev node;}}
}
