Tuesday, February 3, 2015

LeetCode [146] LRU Cache

146. LRU Cache
Medium

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up:
Could you do get and put in O(1) time complexity?

 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

 

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 3000
  • 0 <= value <= 104
  • At most 3 * 104 calls will be made to get and put.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class LRUCache {
    struct ND
    {
        int k, v;
        ND* prev;
        ND* next;
        ND(int _k, int _v):k(_k), v(_v), prev(NULL), next(NULL){}
        ND():prev(NULL), next(NULL){}
    };
    ND* H;
    ND* T;
    int sz, cap;
    unordered_map<int, ND*> mp;//key, ND

    void add(ND* nd){
        T->prev->next = nd;
        nd->prev = T->prev;
        nd->next = T;
        T->prev = nd;
    }
    
    int rm(ND* nd)
    {
        int k = nd->k;
        nd->prev->next = nd->next;
        nd->next->prev = nd->prev;
        return k;
    }

    void mv2end(ND* nd)
    {
        rm(nd);
        add(nd);
    }
public:
    LRUCache(int capacity) {
        H = new ND();
        T = new ND();
        H->next = T;
        T->prev = H;
        sz = 0;
        cap = capacity;
    }
    
    int get(int key) {
        if(mp.find(key)==mp.end()){
            return -1;
        }else{
            ND* nd = mp[key];
            mv2end(nd);
            return nd->v;
        }
    }
    
    void put(int key, int value) {
        if(mp.find(key)!=mp.end()){
            ND* nd = mp[key];
            nd->v = value;
            mv2end(nd);
        }else{
            ND* nd = new ND(key, value);
            add(nd);
            mp[key] = nd;
            if(sz<cap){ 
                sz++;
            }else{
                ND* head = H->next;
                rm(head);
                mp.erase(head->k);
            }
        }
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class LRUCache {
  
  Node head = new Node(0, 0), tail = new Node(0, 0);
  Map<Integer, Node> map = new HashMap();
  int capacity;
  
  public LRUCache(int _capacity) {
    capacity = _capacity;
    head.next = tail;
    tail.prev = head;
  }

  public int get(int key) {
    if(map.containsKey(key)) {
      Node node = map.get(key);
      remove(node);
      insert(node);
      return node.value;
    } else {
      return -1;
    }
  }

  public void put(int key, int value) {
    if(map.containsKey(key)) {
      remove(map.get(key));
    }
    if(map.size() == capacity) {
      remove(tail.prev);
    }
    insert(new Node(key, value));
  }
  
  private void remove(Node node) {
    map.remove(node.key);
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  
  private void insert(Node node){
    map.put(node.key, node);
    Node headNext = head.next;
    head.next = node;
    node.prev = head;
    headNext.prev = node;
    node.next = headNext;
  }
  
  class Node{
    Node prev, next;
    int key, value;
    Node(int _key, int _value) {
      key = _key;
      value = _value;
    }
  }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
at

No comments:

Post a Comment