LeetCode_146 LRUCache (链表题)

题目地址：https://leetcode-cn.com/problems/lru-cache/

题目：

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

试题分析：

这道题考察的是链表的一个综合应用，LRU算法大家都知道，核心思想就是当LRUCache中命中的时候返回该值，并将该值移到LRU链表的头节点，如果没有命中返回异常值；在向LRUCache中put值时需要判断Cache中有没有该值，如果已经有了则返回该值并将该值放到链表头，如果没有该值则要判断链表有没有满，如果链表已满则删除链表尾的节点再将新节点插入链表头，如果链表未满则直接插入到链表头。

整个过程听起来不难，不过在实现过程中，光有一个LRU链表的话实现起来没法做到O(1)，我们都知道在链表中查找值是O(n)的时间复杂度，无法做到O(1),这里就需要借助于一个HashMap，将链表中所有的cache节点都放在HashMap中，在每次对LRUCache进行操作的时候都需要先通过HashMap进行判断在cache中是否已经包含该值，HashMap的随机读时间复杂度是O(1)。具体代码逻辑可以直接看下面代码实现，逻辑就是上面提到的算法思路。

代码：

public class LRUCache_146 {
    private List<CacheNode> cacheList;
    private Map<Integer, CacheNode> cacheMap;
    private int capacity;

    public LRUCache_146(int capacity) {
        cacheList = new LinkedList<CacheNode>();
        cacheMap = new HashMap<Integer, CacheNode>(capacity);
        this.capacity = capacity;
    }

    public int get(int key) {
        if(cacheMap.containsKey(key)){
            cacheList.remove(cacheMap.get(key));
            cacheList.add(0, cacheMap.get(key));
            return cacheMap.get(key).value;
        }else{
            return -1;
        }
    }

    public void put(int key, int value) {
        if(cacheMap.containsKey(key)){
            cacheList.remove(cacheMap.get(key));
            cacheList.add(0, cacheMap.get(key));
        }else{
            //如果cache中没有该值则插入
            if(cacheMap.size()==capacity){
                //cache已满则需要先删除末尾节点再将新值插入队头
                cacheMap.remove(cacheList.get(cacheList.size()-1).key);
                cacheList.remove(cacheList.size()-1);
                CacheNode node = new CacheNode(key,value);
                cacheMap.put(key, node);
                cacheList.add(0, node);
            }else{
                CacheNode node = new CacheNode(key,value);
                cacheMap.put(key, node);
                cacheList.add(0, node);
            }
        }
    }

    private class CacheNode{
        int key;
        int value;
        public CacheNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
}

源码路径：com.monkey01.linkedlist.LRUCache_146

配套测试代码路径：test目录com.monkey01.linkedlist.LRUCache_146Test

https://github.com/feiweiwei/LeetCode4Java.git