LRUCache! 干就完了

今天面了拼多多，LRUCache再次出现在了我的面前，面对这个半年以来面对最多的面试代码问题，我再次给出我的解决方案：

1、链表

使用链表作为最主要的数据结构，将数据按照先后顺序在链表尾部插入，直到满了开始从头减去链表，时间复杂度分析分别为：

使用单向链表，get需要找到我们要的cache所在位置，因此时间复杂度为O(n),add由于需要先判断是否已经存在，所以需要调用get方法，在满的时候需要remove，所以虽然删除时间复杂度为O(1)，整体时间复杂度为O(n),而remove从头部删除时间复杂度为O(1)但是在中间的时候需要做get操作，时间复杂度依旧为O(n)。使用双向链表可以降低add()时间复杂度，但是整体来说时间复杂度在O(n).

代码实现如下：

class LRUCacheLinkedList<K,V>{
        int capcity;
        HashMap<K,V> data;
        LinkedList<K> list;
        public  LRUCacheLinkedList(int capcity){
            data = new HashMap<>(capcity);
            list = new LinkedList<>();
            this.capcity = capcity;
        }

        public V get(K key){
            if(data.containsKey(key)) return data.get(key);
            else return null;
        }

        public Boolean add(K key, V value){
            if(data.containsKey(key)){
                data.put(key,value);
                list.remove(list.indexOf(key));
                list.add(key);
            }
            else {
                if(data.size() < capcity){
                    list.add(key);
                }
                else {
                    list.remove(0);
                    list.add(key);
                }
            }
            return true;
        }
        public V remove(K key){
            list.remove(list.indexOf(key));
            V res = data.getOrDefault(key, null);
            data.remove(key);
            return res;
        }
    }

这里面主要的时间复杂度在于在链表get方法，时间复杂度为O(1);

2、HashMap + LinkedList

使用双向链表保存数据，使用HashMap保存数据在LinkedList中的位置，使用HashMap保存key值和key值对应的DLinkNode时间复杂度如下：

代码实现如下，有的小朋友可能会问了：显得叔叔显得叔叔为什么要手写DlinkNode，java的LinkedList不就是双向链表吗？

这个小朋友问的就非常好，为什么要手写呢？因为如果看过LinkedList代码的话就会发现LinkedList的Node类是private static修饰的，我想拿也拿不到，所以就会自己写。

 class LRUCacheHashMap<K,V> {
        /*为什么不用LinkeList的Node类，非要自己写？
        因为LinkeList的Node类是private static的，所以要是想要用获得Node的地址就得自己实现
        * */
            class DLinkedNode {
                V value;
                DLinkedNode prev;
                DLinkedNode next;
                public DLinkedNode() {}
                public DLinkedNode( V _value) {value = _value;}
            }

            private Map<K, DLinkedNode> cache = new HashMap<>();
            private int size;
            private int capacity;
            private DLinkedNode head, tail;

            public LRUCacheHashMap(int capacity) {
                this.size = 0;
                this.capacity = capacity;
                // 使用伪头部和伪尾部节点
                head = new DLinkedNode();
                tail = new DLinkedNode();
                head.next = tail;
                tail.prev = head;
            }

            public V get(int key) {
                DLinkedNode node = cache.get(key);
                if (node == null) {
                    return null;
                }
                // 如果 key 存在，先通过哈希表定位，再移到头部
                moveToHead(node);
                return node.value;
            }

            public void put(K key, V value) {
                DLinkedNode node = cache.get(key);
                if (node == null) {
                    // 如果 key 不存在，创建一个新的节点
                    DLinkedNode newNode = new DLinkedNode( value);
                    // 添加进哈希表
                    cache.put(key, newNode);
                    // 添加至双向链表的头部
                    addToHead(newNode);
                    ++size;
                    if (size > capacity) {
                        // 如果超出容量，删除双向链表的尾部节点
                        DLinkedNode tail = removeTail();
                        // 删除哈希表中对应的项
                        cache.remove(key);
                        --size;
                    }
                }
                else {
                    // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
                    node.value = value;
                    moveToHead(node);
                }
            }

            private void addToHead(DLinkedNode node) {
                node.prev = head;
                node.next = head.next;
                head.next.prev = node;
                head.next = node;
            }

            private void removeNode(DLinkedNode node) {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }

            private void moveToHead(DLinkedNode node) {
                removeNode(node);
                addToHead(node);
            }

            private DLinkedNode removeTail() {
                DLinkedNode res = tail.prev;
                removeNode(res);
                return res;
            }
        }

但是记住碰到面试官问LRUCache不要直接写奥，要先写一个O(n)的，然后让他启发你，你再把O(1)的写出来，秋招小心机get~!