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.
Example
思路
维护一个HashMap和一个双向链表。
一个key对应到一个node。
每次get或者set的时候，把当前处理的node放到链表的尾巴上（most recent）。
如果链表满了，就把头上的那个node（least recent）删掉，并且在HashMap里也把对应的key删掉。
对于双向链表的处理，用一个dummy head和一个dummy tail，对于写程序会方便很多。
Code
class ListNode { int key; int val; ListNode prev; ListNode next; public ListNode(int key, int val) { this.key = key; this.val = val; this.prev = null; this.next = null; } } public class Solution { private int capacity; private ListNode head; private ListNode tail; private HashMap<Integer, ListNode> map; // @param capacity, an integer public Solution(int capacity) { // write your code here this.capacity = capacity; head = new ListNode(-1, -1); tail = new ListNode(-1, -1); head.next = tail; tail.prev = head; map = new HashMap<>(); } // @return an integer public int get(int key) { // write your code here if (!map.containsKey(key)) { return -1; } ListNode node = map.get(key); node.prev.next = node.next; node.next.prev = node.prev; moveToTail(node); return node.val; } // @param key, an integer // @param value, an integer // @return nothing public void set(int key, int value) { // write your code here if (get(key) != -1) { map.get(key).val = value; return; } if (map.size() == this.capacity) { map.remove(head.next.key); head.next = head.next.next; head.next.prev = head; } ListNode node = new ListNode(key, value); map.put(key, node); moveToTail(node); } public void moveToTail(ListNode node) { node.prev = tail.prev; tail.prev.next = node; tail.prev = node; node.next = tail; } }
