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.
https://oj.leetcode.com/problems/lru-cache/
思路：实现一个LRUCache的类，主要是get和set方法要保证高效。需要一个hashmap 和一个双向链表结合。hashmap用于在O(1)的时间内查找指定元素是否在cache里，而双向链表则允许在O(1)的时间移动元素到表头和删除尾部节点。
import java.util.HashMap; public class LRUCache { private int capacity; private int len; private HashMap<Integer, DoubleLinkedListNode> map = new HashMap<Integer, DoubleLinkedListNode>(); private DoubleLinkedListNode head; private DoubleLinkedListNode tail; public LRUCache(int capacity) { this.capacity = capacity; len = 0; } public int get(int key) { if (map.containsKey(key)) { DoubleLinkedListNode cur = map.get(key); removeNode(cur); setHead(cur); return cur.val; } else return -1; } public void set(int key, int value) { if (map.containsKey(key)) { DoubleLinkedListNode cur = map.get(key); cur.val = value; removeNode(cur); setHead(cur); } else { DoubleLinkedListNode newNode = new DoubleLinkedListNode(key, value); if (len < capacity) { setHead(newNode); map.put(key, newNode); len++; } else { map.remove(tail.key); tail = tail.pre; if (tail != null) tail.next = null; setHead(newNode); map.put(key, newNode); } } } private void removeNode(DoubleLinkedListNode cur) { if (cur == null) return; DoubleLinkedListNode pre = cur.pre; DoubleLinkedListNode next = cur.next; if (pre != null) { pre.next = cur.next; } else head = next; if (next != null) next.pre = cur.pre; else tail = pre; } private void setHead(DoubleLinkedListNode cur) { cur.next = head; cur.pre = null; if (head != null) head.pre = cur; head = cur; if (tail == null) tail = cur; } public static void main(String[] args) { LRUCache cache = new LRUCache(1); cache.set(1, 11); cache.set(1, 111); System.out.println(cache.get(1)); cache.set(2, 22); System.out.println(cache.get(1)); System.out.println(cache.get(2)); } private static class DoubleLinkedListNode { public int key; public int val; public DoubleLinkedListNode pre; public DoubleLinkedListNode next; public DoubleLinkedListNode(int key, int val) { this.key = key; this.val = val; } } }
参考：
http://www.programcreek.com/2013/03/leetcode-lru-cache-java/
http://blog.csdn.net/whuwangyi/article/details/15495845
[leetcode] LRU Cache,布布扣,bubuko.com
原文：http://www.cnblogs.com/jdflyfly/p/3830446.html