LeetCode[3] - LRU Cache

当李特第一次把这题拿出来的时候，我是慌的。
啥是LRU Cache啊？ 接下去看吧。

后来，我很天真的来了一个O(n) 的解法，结果果然时间过多。天真解法很简单啊：一个map<key,value>存数值。一个queue<key>来存排位。每次有更新，就把最新的放在末尾；每次超过capaticity,就把大头干掉。很简单嘛，但是跑起来太久，失败了。

于是就来了第二个做法。其实还是跟方法一是类似的。只不过用了一个特别的双向的LinkNode，有了head和tail，这样就大大加快了速度。主要加快的就是那个‘更新排位’的过程，过去我是O(n),现在O(1)就好了。具体看下面。

巧妙点：

1. head和tail特别巧妙：除掉头和尾，和加上头和尾，就都特别快。
2. 用双向的pointer: pre和next， 当需要除掉任何一个node的时候，只要知道要除掉哪一个，直接把node.pre和node.next耐心连起来就好了，node就自然而然的断开不要了。

李特的这个Design的题目很有意思。果然值得被作为Hard。但是一旦知道怎么解决了，就不是很特别，因为并不是难想的算法。

/*
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.

Tags: Design

*/
/*
It looks like we need to do some design, according to (http://www.cnblogs.com/yuzhangcmu/p/4113462.html). Though, the solution's concept is quite similar as attempt1.

1. The design uses HashMap, and 2-way LinkedList. Map<key, LinkNode>
2. Use two dummy node: head and tail. When add/remove nodes, we are add/remove nodes in between head and tail.
    So. head.next is our real 1st element
    andd tail.pre is our real last element

Note:
Be careful: when removing a node due to capacity issue, remember to remove both 1st node(head.next) and the corresponding entry in the map: map.remove(head.next.key)
*/
public class LRUCache {
    private class LinkNode {
        int key;
        int val;
        LinkNode pre = null;
        LinkNode next = null;
        LinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private int cap;
    private HashMap<Integer, LinkNode> map;
    private LinkNode head;
    private LinkNode tail;
    public LRUCache(int capacity) {
        this.cap = capacity;
        this.map = new HashMap<Integer, LinkNode>();
        this.head = new LinkNode(-1, -1);
        this.tail = new LinkNode(-1, -1);
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            LinkNode temp = map.get(key);
            moveUsedToTail(temp);
            return temp.val;
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            LinkNode temp = map.get(key);
            temp.val = value;
            moveUsedToTail(temp);   
        } else {
            if (map.size() >= cap) {
                map.remove(head.next.key);
                removeHead();
            }
            LinkNode newNode = new LinkNode(key, value);
            addTail(newNode);
            map.put(key, newNode);
        }
    }
    
    public void moveUsedToTail(LinkNode node) {
        removeNode(node);
        addTail(node);
    }

    public void removeHead(){//O(1)
        removeNode(head.next);
    }
    public void addTail(LinkNode node){//O(1)
        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
    }
    public void removeNode(LinkNode node) {//O(1)
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}

/*
First Attempt: time exceeds

Thoughts:
Easy to implement: cache the least-added item. However, we are looking for the cache of 'leaset-recently-used item'.

'used' means the get() method:
whenever get, remove that key from the queue, and move that key to top.

Time Cost: O(n) on get(), set()


*/

public class LRUCache {
    private int cap;
    private HashMap<Integer, Integer> map;
    private LinkedList<Integer> queue;
    public LRUCache(int capacity) {
        this.cap = capacity;
        this.map = new HashMap<Integer, Integer>();
        this.queue = new LinkedList<Integer>();
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            moveUsedToTop(key);
            return map.get(key);
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            moveUsedToTop(key);
            map.put(key, value);
        } else {
            if (queue.size() >= cap) {
                map.remove(queue.poll());
            }
            queue.offer(key);
            map.put(key, value);
        }
        
    }
    //O(n)
    public void moveUsedToTop(int key) {
        for (int i = 0; i < queue.size(); i++) {
            if (queue.get(i) == key) {
                queue.remove(i);
                queue.offer(key);
                break;
            }
        }
    }
}