张伦聪的技术博客 Research And Development

146. LRU缓存机制

2018-09-23

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

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

¥ 打赏博主

类似文章

上一篇 52. N皇后 II

留言