首页 > 代码库 > 146. LRU Cache

146. LRU Cache

2024-09-22 06:35:31   215人阅读

题目：

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. 

链接： http://leetcode.com/problems/lru-cache/

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<Integer, Node> 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<Integer, Node>();
20         this.head = new Node(-1, -1);
21         this.tail = new Node(-1, -1);
22         // initialize head / tail
23         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 node
31             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 first
45             if (map.size() == this.capacity) {
46                 // remove last node from map
47                 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

https://discuss.leetcode.com/topic/43961/laziest-implementation-java-s-linkedhashmap-takes-care-of-everything

https://discuss.leetcode.com/topic/17433/probably-the-best-java-solution-extend-linkedhashmap

更多讨论

https://discuss.leetcode.com/category/154/lru-cache

146. LRU Cache


联系
我们