实现lru 缓存
LRU CacheTotal Accepted:35641Total Submissions:241374My Submissions
QuestionSolution
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:getandset.
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.
Show Tags
public class LRUCache {static class Node {int key;int value;@Overridepublic String toString() {return "Node{" +"key=" + key +", value=" + value +'}';}}static private LinkedList<Node> cache;static private int cap;static private Node indexMap[];public LRUCache(int capacity) {cache = new LinkedList<Node>();indexMap = new Node[100000];cap = capacity;}static public boolean isFull() {return cache.size() == cap;}static public Node find(int key) {if (cache.isEmpty())return null;Node tar = null;if ((tar = indexMap[key]) == null)return null;cache.remove(tar);cache.addFirst(tar);return tar;}public int get(int key) {Node node = find(key);if (node == null) {return -1;}return node.value;}public void set(int key, int value) {Node node = null;if ((node = find(key)) != null) {node.value = value;return;}//not find the elementif (isFull()) {indexMap[cache.getLast().key] = null;cache.removeLast();}Node newNode = new Node();newNode.key = key;newNode.value = value;cache.addFirst(newNode);indexMap[key] = newNode;}}
，以后我会去到很多很繁华或苍凉，
