Massive Algorithms: LeetCode 146

LeetCode 146 - LRU Cache

Related:
LeetCode 146 - LRU Cache
LeetCode 460 - LFU Cache
LeetCode – LRU Cache (Java)
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

The key to solve this problem is using a double linked list which enables us to quickly move nodes.
The LRU cache is a hash table of keys and double linked nodes.

https://github.com/shogunsea/lintcode/blob/master/lru-cache.java
doubly linked list, hash map
http://www.cnblogs.com/springfor/p/3869393.html
http://www.jiuzhang.com/solutions/lru-cache/

public class LRUCache {
    private class Node{
        Node prev;
        Node next;
        int key;
        int value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

    public int get(int key) {
        if( !hs.containsKey(key)) {
            return -1;
        }

        // remove current
        Node current = hs.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        // move current to tail
        move_to_tail(current);

        return hs.get(key).value;
    }

    public void set(int key, int value) {
        if( get(key) != -1) {
            hs.get(key).value = value;
            return;
        }

        if (hs.size() == capacity) {
            hs.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);
        hs.put(key, insert);
        move_to_tail(insert);
    }

    private void move_to_tail(Node current) {
        current.prev = tail.prev;
        tail.prev = current;
        current.prev.next = current;
        current.next = tail;
    }
}

http://www.cnblogs.com/yuzhangcmu/p/4113462.html

使用 HashMap+ 双向链表实现：

1. 如果需要移除老的节点，我们从头节点移除。

2. 如果某个节点被访问（SET/GET），将其移除并挂在双向链表的结尾。

3. 链表满了后，我们删除头节点。

4. 最近访问的节点在链尾。最久被访问的节点在链头。

https://gist.github.com/gcrfelix/2ff8f7da188785b4c471
public class LRUCache {
// https://alaindefrance.wordpress.com/2014/10/05/lru-cache-implementation/
// 一定要能解释清楚为什么在这儿用Hashtable和doubly linkedlist
// 首先这是一个cahe，所以为了保证read and write data是O(1)，hashtable是一个good choice
// 但是hashtable不能满足keep order的需求，没办法把least used data放在最前面，所以想到doubly linkedlist,
// doubly linkedlist的好处是easy to move a given node to the tail(比起queue来)

// 这个数据结构比较复杂，是用一个hash表加上一个双向链表来实现。
// HashMap用来存储key和节点；双向链表用来存储节点位置，主要用来当HashMap达到capacity时,
// invalidate the least recently used item before inserting a new item.

// 这里的doubly linked list排在越前面的node越是least recently used，所以在使用set方法时如果超过capacity就会remove head后面的第一个node
// 并且使用get和set方法时用到的node会被move到tail，这说明越往后的node越是most recently used
// 为什么要把most recently used的node放在tail呢？因为这样超过capacity时方便删除开头的node

private class Node {
Node prev;
Node next;
int key;
int value;

public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}

private int capacity;
private HashMap<Integer, Node> hash = new HashMap<Integer, Node>();
private Node head = new Node(-1,-1);
private Node tail = new Node(-1,-1);

public LRUCache(int capacity) {
this.capacity = capacity;
tail.prev = head;
head.next = tail;
}

public int get(int key) {
if(!hash.containsKey(key)) {
return -1;
}

// remove current
Node current = hash.get(key);
current.next.prev = current.prev;
current.prev.next = current.next;

// move current to tail, most recently used的node要移到tail
move_to_tail(current);

return current.value;
}

public void set(int key, int value) {
if(get(key) != -1) { // 注意这边一定要用get(key)而不能用hash.containsKey(key), 因为用get(key)可以把该key的node放到tail而后者不能
hash.get(key).value = value;
return; // 注意这边要加return, 否则报错
}
// When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item
if(hash.size() == capacity) {
hash.remove(head.next.key);
head.next = head.next.next;
head.next.prev = head;
}

Node node = new Node(key, value);
hash.put(key, node);
move_to_tail(node); // 注意：当新的item被insert进来后，把它放入双向链表的最后，因为它是most recently used
}

private void move_to_tail(Node current) {
// first deal with all 'prev' relations
current.prev = tail.prev;
tail.prev = current;
// then deal with all 'next' relations
current.prev.next = current;
current.next = tail;
}
}
http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

public class LRUCache {
 private HashMap<Integer, DoubleLinkedListNode> map 
  = new HashMap<Integer, DoubleLinkedListNode>();
 private DoubleLinkedListNode head;
 private DoubleLinkedListNode end;
 private int capacity;
 private int len;
 
 public LRUCache(int capacity) {
  this.capacity = capacity;
  len = 0;
 }
 
 public int get(int key) {
  if (map.containsKey(key)) {
   DoubleLinkedListNode latest = map.get(key);
   removeNode(latest);
   setHead(latest);
   return latest.val;
  } else {
   return -1;
  }
 }
 public void removeNode(DoubleLinkedListNode node) {
  DoubleLinkedListNode cur = node;
  DoubleLinkedListNode pre = cur.pre;
  DoubleLinkedListNode post = cur.next;
 
  if (pre != null) {
   pre.next = post;
  } else {
   head = post;
  }
 
  if (post != null) {
   post.pre = pre;
  } else {
   end = pre;
  }
 }
 
 public void setHead(DoubleLinkedListNode node) {
  node.next = head;
  node.pre = null;
  if (head != null) {
   head.pre = node;
  }
 
  head = node;
  if (end == null) {
   end = node;
  }
 }
 
 public void set(int key, int value) {
  if (map.containsKey(key)) {
   DoubleLinkedListNode oldNode = map.get(key);
   oldNode.val = value;
   removeNode(oldNode);
   setHead(oldNode);
  } else {
   DoubleLinkedListNode newNode = 
    new DoubleLinkedListNode(key, value);
   if (len < capacity) {
    setHead(newNode);
    map.put(key, newNode);
    len++;
   } else {
    map.remove(end.key);
    end = end.pre;
    if (end != null) {
     end.next = null;
    }
 
    setHead(newNode);
    map.put(key, newNode);
   }
  }
 }
}
 
class DoubleLinkedListNode {
 public int val;
 public int key;
 public DoubleLinkedListNode pre;
 public DoubleLinkedListNode next;
 
 public DoubleLinkedListNode(int key, int value) {
  val = value;
  this.key = key;
 }
}

X. https://leetcode.com/articles/lru-cache/

class LRUCache {

LinkedHashMap<Integer, Integer> cache;

int capacity;

public LRUCache(int capacity) {

this.capacity = capacity;

cache = new LinkedHashMap<Integer, Integer>(capacity);

}

public void move_to_end(int key) {

int value = cache.get(key);

cache.remove(key);

cache.put(key, value);

}

public void remove_first() {

cache.remove(cache.entrySet().iterator().next().getKey());

}

public int get(int key) {

if (! cache.containsKey(key)) return -1;

move_to_end(key);

return cache.get(key);

}

public void put(int key, int value) {

if (cache.containsKey(key)) move_to_end(key);

cache.put(key, value);

if (cache.size() == capacity + 1) remove_first();

}

http://blueocean-penn.blogspot.com/2015/09/least-recently-used-cache-lru.html
http://allenlipeng47.com/PersonalPage/index/view/182/nkey
Use JDK LinkedHashMap
https://discuss.leetcode.com/topic/43961/laziest-implementation-java-s-linkedhashmap-takes-care-of-everything

In the constructor, the third boolean parameter specifies the ordering mode. If we set it to true, it will be in access order. (https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#LinkedHashMap-int-float-boolean-)
By overriding removeEldestEntry in this way, we do not need to take care of it ourselves. It will automatically remove the least recent one when the size of map exceeds the specified capacity.(https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#removeEldestEntry-java.util.Map.Entry-)

    public class LRUCache {
        private LinkedHashMap<Integer, Integer> map;
        private final int CAPACITY;
        public LRUCache(int capacity) {
            CAPACITY = capacity;
            map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return size() > CAPACITY;
                }
            };
        }
        public int get(int key) {
            return map.getOrDefault(key, -1);
        }
        public void set(int key, int value) {
            map.put(key, value);
        }
    }

https://leetcode.com/discuss/42891/probably-the-best-java-solution-extend-linkedhashmap
public class LRUCache { private Map<Integer, Integer> map; public LRUCache(int capacity) { map = new LinkedHashMap<Integer, Integer>(16, 0.75f, true) { protected boolean removeEldestEntry(Map.Entry eldest) { return size() > capacity; } }; } public int get(int key) { return map.getOrDefault(key, -1); } public void set(int key, int value) { map.put(key,value); } }
http://www.acmerblog.com/leetcode-lru-cache-lru-5745.html

4public class LRUCache extends LinkedHashMap<Integer, Integer> {

05    private int capacity;

06

07    public LRUCache(int capacity) {

08        super(16, 0.75f, true);

09        this.capacity = capacity;

10    }

11    //重写父类get，为null时范围-1

12    public Integer get(Object key) {

13        Integer v = super.get(key);

14        if (v != null)

15            return v;

16        else

17            return -1;

18    }

19    //重写父类方法，当超过缓存容量时，就删除最老的

20    public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {

21        return size() > capacity;

22    }

23

24    public void set(int key, int value) {

25        super.put(key, value);

26    }

27}

Implement an ISBN cache
LRUCache.cpp LRUCache.java
Key Point:
Use Hashmap to access element in O(1) time, and stores according node from Linkedlist, so we can easily access or change Linkedlist.
Use LinkedList to maintain access/insert order,
public class LRUCache {
public int lookupVal = 0;
private int capacity;
private HashMap<Integer, Pair<LinkedList<Integer>.Node, Integer>> cache = new HashMap<>();
private LinkedList<Integer> data = new LinkedList<Integer>();

public LRUCache(int c) {
capacity = c;
}

public boolean lookup(int isbn) {
Pair<LinkedList<Integer>.Node, Integer> it = cache.get(isbn);
if (it == null) {
return false;
}

lookupVal = it.getSecond();
moveToFront(isbn, it);
return true;
}

void insert(int isbn, int price) {
Pair<LinkedList<Integer>.Node, Integer> it = cache.get(isbn);
if (it != null) {
moveToFront(isbn, it);
} else {
// Remove the least recently used.
if (cache.size() == capacity) {
cache.remove(data.back());
}
cache.put(
isbn,
new Pair<LinkedList<Integer>.Node, Integer>(data
.pushFront(isbn), price));
}
}

public boolean erase(int isbn) {
Pair<LinkedList<Integer>.Node, Integer> it = cache.get(isbn);
if (it == null) {
return false;
}

data.erase(it.getFirst());
cache.remove(isbn);
return true;
}

// Move the most recent accessed item to the front.
void moveToFront(int isbn, Pair<LinkedList<Integer>.Node, Integer> it) {
data.erase(it.getFirst());
data.pushBack(isbn);
it.setFirst(data.front());
}
}

public class LinkedList<T> {

public class Node {

public T item;

private Node next;

private Node prev;

}

private int N; // count

private Node pre; // sentinel before first item

private Node post; // sentinel after last item

public LinkedList() {

pre = new Node();

post = new Node();

pre.next = post;

post.prev = pre;

}

https://github.com/shogunsea/lintcode/blob/master/lru-cache.java
http://www.geeksforgeeks.org/implement-lru-cache/
深入Java集合学习系列：LinkedHashMap的实现原理

F*B店面
饭店老板接收电话订餐，怎么接收电话号码删除电话号码拿出第一个电话号码。double LN + hashmap, O(1) time O(n) space
不用考虑容量简单很多实现add poll remove

没有key

1. 饭店⽼老老板接收电话订餐，怎么接收电话号码删除电话号码拿出第⼀一个
电话号码
2. 设计⼀一⼀一个class，实现以下abstract:
void put(Key k, Value, v); // 不不存在添加，存在覆盖
Key get(Key k); // 不不存在返回null
void delete(Key k); // 删除key及其value
Key last(); // 返回在此之前所有put,get操作中，最后⼀一个access的
Key。
⽐比如: put(a,b) put(c,d) get(a) delete(c) ; last(): a

LeetCode 146 - LRU Cache

Labels

Popular Posts