首页 > 代码库 > LeetCode解题报告:LRU Cache
LeetCode解题报告:LRU Cache
LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
思路：Java的LinkedHashMap可以实现最近最少使用(LRU)的次序。类似于HashMap。详见《JAVA编程思想(第4版)》P487.
题目要求是一个固定大小的cache，因此需要一个变量maxCapacity来记录容量大小，用LinkedHashMap存储数据。在添加数据set()方法时，判断一下是否达到maxCapacity，如果cache已经满了，remove掉最长时间不使用的数据，然后put进新的数据。
题解：
import java.util.LinkedHashMap;public class LRUCache { LinkedHashMap<Integer, Integer> linkedmap; int maxCapacity; public LRUCache(int capacity) { this.maxCapacity = capacity; this.linkedmap = new LinkedHashMap<Integer, Integer>(capacity, 1f, true); } public int get(int key) { if (linkedmap.containsKey(key)) return linkedmap.get(key); else return -1; } public void set(int key, int value) { int size = linkedmap.size(); if ((size < maxCapacity) || (linkedmap.containsKey(key))) { linkedmap.put(key, value); } else if (size >= maxCapacity) { Iterator<Integer> it = linkedmap.keySet().iterator();//iterator method is superior the toArray(T[] a) method. linkedmap.remove(it.next()); linkedmap.put(key, value); } }}结题遇到的问题：
1.下面这段代码提交的时候超时了。
import java.util.LinkedHashMap;public class LRUCache { LinkedHashMap<Integer, Integer> linkedmap; int maxCapacity; public LRUCache(int capacity) { this.maxCapacity = capacity; this.linkedmap = new LinkedHashMap<Integer, Integer>(capacity, 1f, true); } public int get(int key) { if (linkedmap.containsKey(key)) return linkedmap.get(key); else return -1; } public void set(int key, int value) { int size = linkedmap.size(); if ((size < maxCapacity) || (linkedmap.containsKey(key))) { linkedmap.put(key, value); } else if (size >= maxCapacity) { Integer[] keyArray = linkedmap.keySet().toArray(new Integer[0]);//这是超时的代码，采用Iterator不会超时。 linkedmap.remove(keyArray[0]); linkedmap.put(key, value); } }}2.Roger自己实现LinkedHashMap的功能，采用双向链表和哈希表。效率略低于LinkedHashMap.(644ms>548ms)
import java.util.HashMap;public class LRUCache { private HashMap<Integer, Entry<Integer>> index; private UDFList<Integer> data; public LRUCache(int capacity) { index = new HashMap<Integer, Entry<Integer>>(capacity); data = http://www.mamicode.com/new UDFList(capacity);>