题目：

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. 

链接： 

5/14/2017

准备面试

用hashmap + double linkedlist实现，hashmap里key是key, value是double linkedlist里面的node节点

注意的问题：

1. 最好不用系统的Deque来做double linkedlist，不容易储存node

2. double linkedlist里的node包括key, value, prev, next

3. 可以不需要额外的size而直接用map的size和capacity做比较

4. head, tail可以设成dummy node，简化最开始的判断

5. put包含get，可以省略一些步骤

6. 第31，32行是将旧的值所在的node从double linkedlist当中取出来，相当于remove出来，之后往里加的时候只需要按照一般的情况来就可以了。

7. 第42行可以直接在map.get(key).val = value来更改node的值，当然node的位置在double linkedlist当中需要更改。

1 public class LRUCache { 2     class Node { 3         int key; 4         int val; 5         Node prev; 6         Node next; 7         Node(int key, int val) { 8             this.key = key; 9             this.val = val;10         }11     }12     Map
     
       map;13     Node head;14     Node tail;15     int capacity;16 17     public LRUCache(int capacity) {18         this.capacity = capacity;19         this.map = new HashMap
      
       ();20         this.head = new Node(-1, -1);21         this.tail = new Node(-1, -1);22         // initialize head / tail23         tail.prev = head;24         head.next = tail;25     }26     27     public int get(int key) {28         if (map.containsKey(key)) {29             Node old = map.get(key);30             // why need these two? treat old node as a new node, similar idea as put remove last node31             old.prev.next = old.next;32             old.next.prev = old.prev;33             moveToTail(old);34             return old.val;35         } else {36             return -1;37         }38     }39     40     public void put(int key, int value) {41         if (get(key) != -1) {42             map.get(key).val = value;43         } else {44             // check capacity first45             if (map.size() == this.capacity) {46                 // remove last node from map47                 map.remove(head.next.key);48                 head.next = head.next.next;49                 head.next.prev = head;50             }51             Node node = new Node(key, value);52             moveToTail(node);53             map.put(key, node);54         }55     }56     private void moveToTail(Node node) {57         node.prev = tail.prev;58         tail.prev = node;59         node.prev.next = node;60         node.next = tail;        61     }62 }63 64 /**65  * Your LRUCache object will be instantiated and called as such:66  * LRUCache obj = new LRUCache(capacity);67  * int param_1 = obj.get(key);68  * obj.put(key,value);69  */
      
     

linkedhashmap

更多讨论