146. LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 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

解：题目要求实现O(1)时间复杂度的获取数据和写入数据。哈希表可以实现O(1)复杂度的获取数据，但是没有办法写入数据，因为没有办法判断大小，就不知道这个数据应该写到哪里。双向链表可以以O(1)时间复杂度，很方便地实现数据的插入和删除，但是没有办法直接定位。所以我们采用哈希表和双向链表相结合的方法。之所以选择双向链表而不是单链表，是为了可以从中间任意结点修改链表结构，而不必从头结点开始遍历。

获取数据的时候：如果密钥存在于缓存中，那么返回缓存的value值，同时在列表中将该节点删除并且插入到链表的最前端；如果密钥不存在于缓存中，返回-1。
写入数据的时候：如果密钥存在，在链表中将该结点删除并插入到最前端；如果密钥不存在，如果缓存容量达到上限删除链表的最后一个元素，然后将该节点插入到链表的最前端；哈希表中插入该元素。

以下是纯手打ac解，效率不是很高，可优化的地方，可以再增加一个全局变量双向链表尾部，删除最少用的缓存时可以快速删除；可以再设置一个当前容量变量，无须每次计算链表长度;map里面可以保存一个entry里面保存前后指针和值，这样删除的时候无须从头遍历，最大化使用双向链表优势。我这代码写得有点用单链表的感觉。

参考

class LinkedNode {
    int val;
    LinkedNode pre;
    LinkedNode next;

    LinkedNode(int x) {
        val = x;
    }
}
public class LRUCache {
    //缓存容量
    private int capacity;
    //双向链表实现插入删除的时间复杂度o(1)，保存的值为缓存的key
    //双向链表头部
    private LinkedNode head;
    //哈希表实现查找的O(1)时间复杂度，并保存缓存的key/value
    private HashMap<Integer, Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new LinkedNode(-1);
        this.head.pre = null;
        this.head.next = null;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            //如果缓存存在则更新链表后，返回值
            delLinkedNode(key);
            addLinkedNode(key);
            return map.get(key);
        } else {
            //如果缓存不存在直接返回
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            //如果缓存存在则更新链表后，赋新值
            delLinkedNode(key);
            addLinkedNode(key);
            map.put(key, value);
        } else {
            //如果缓存不存在,未达到上限，插入链表最前端，并且加入map
            if (lenLinkedNode(head) < capacity) {
                addLinkedNode(key);
                map.put(key, value);
            } else {
                //如果缓存不存在,达到上限，删除尾端节点，删除map值，插入链表最前端，并且加入map
                LinkedNode dummy = head;
                while (dummy.next != null) {
                    dummy = dummy.next;
                }
                delLinkedNode(dummy.val);
                addLinkedNode(key);
                map.remove(dummy.val);
                map.put(key, value);
            }

        }
    }

    /**
     * 删除一个节点
     *
     * @param key
     */
    private void delLinkedNode(int key) {
        LinkedNode dummy = head;
        while (dummy.next != null) {
            if (dummy.next.val == key) {
                dummy.next = dummy.next.next;
                if (dummy.next != null) {
                    dummy.next.pre = dummy;
                }
                break;
            } else {
                dummy = dummy.next;
            }
        }
    }

    /**
     * 在链表头部增加一个节点
     *
     * @param key
     */
    private void addLinkedNode(int key) {
        LinkedNode tmp = head.next;
        head.next = new LinkedNode(key);
        head.next.pre = head;
        head.next.next = tmp;
        if (head.next.next != null) {
            head.next.next.pre = head.next;
        }
    }

    /**
     * 计算双向链表长度
     *
     * @param head
     * @return
     */
    private int lenLinkedNode(LinkedNode head) {
        LinkedNode dummy = head;
        int len = 0;
        while (dummy.next != null) {
            len++;
            dummy = dummy.next;
        }
        return len;
    }

    public static void main(String[] args) {
        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
    }
}

类似文章

留言