插话：只写了几个连续的博客，博客排名不再是实际“远在千里之外”该。我们已经进入2一万内。

再接再厉。油！

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.

【题意】

设计并实现一个支持get和set操作的缓存：

get(key) - 存在时返回其值。否则返回-1。

set(key) - 不存在时插入新值。存在时更新其值。注意当容量满时，需删除最长时间没有訪问的key。将其删除。并插入新的key。

==================== Map+List 实现法 ====================

【思路】

用map结构实现<key, value>的存储与读取。

用一个list来记录key被訪问时间的久远。近期被訪问的放在list的最后。list中的第一个key表示最长时间没被訪问的。

【Java代码】

class LRUCache {

    HashMap<Integer, Integer> map;

    ArrayList<Integer> list;

    int capacity;

    public LRUCache(int capacity) {

        map = new HashMap<Integer, Integer>(capacity);

        list = new ArrayList<Integer>(capacity);

        this.capacity = capacity;

    }

    public int get(int key) {

        if (map.get(key) == null) return -1;

        list.remove(new Integer(key));

        list.add(key);

        return map.get(key);

    }

    public void set(int key, int value) {

    	if (map.get(key) != null) {//原来存在key

    		map.put(key, value);

    		list.remove(new Integer(key));

            list.add(key);

    	} else {//原来不存在key

    		if (map.size() < capacity) {//容量不满

    			map.put(key, value);

    			list.add(key);

    		} else {//容量满

    			int leastkey = list.remove(0);

                list.add(key);

                map.remove(leastkey);

                map.put(key, value);

    		}

    	}

    }

}

【注意点】

题目要求是Least Recently Used，不仅 set 时要更新list，get 时也要更新list。

set 时。需先推断map中有无该值，若没有再推断map是否满了；假设反过来，即先推断map是否为满，再推断map中有无该值。这样就错了。

由于假设map满时，当中有该值。直接更新就好，而先推断map是否为满的话。就会导致删除最长时间没有被訪问的值。

【常规解法】

通经常使用的元素双向链表来记录不被访问的时间最长，由于双向链表可以O(1)达到一定时间内移动的节点，删除头和尾节点。

在上面的代码list实现，其remove当实际遍历整个list为了找到一个节点。

LeetCode没有时间作要求，采访中肯定会要求。