Leetcode NO.146 lru-cache LRU Cache 最近最少使用实现

目录

• 1.问题描述
• 2.测试用例
  • 示例 1
• 3.提示
• 4.代码
  • 1.继承LinkedHashMap实现
    • code
    • 复杂度
  • 2.HashMap && DoubleLinklist

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

输入

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出

[null, null, null, 1, null, -1, null, -1, 3, 4]

解释

LRUCache lRUCache = new LRUCache(2);

lRUCache.put(1, 1); // 缓存是 {1=1}

lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}

lRUCache.get(1); // 返回 1

lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}

lRUCache.get(2); // 返回 -1 (未找到)

lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}

lRUCache.get(1); // 返回 -1 (未找到)

lRUCache.get(3); // 返回 3

lRUCache.get(4); // 返回 4

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

public class LRU_Cache_With_LinkedHashMap extends LinkedHashMap<Integer, Integer> {


    private int capacity;

    public LRU_Cache_With_LinkedHashMap(int initialCapacity) {
        /**
         * initialCapacity 容量
         * loadFactor 扩容因子
         * accessOrder false 不删除，
         */
        super(initialCapacity, 0.75f, true);
        this.capacity = initialCapacity;
    }


    @Override
    public Integer get(Object key) {
        return super.get(key) == null ? -1 : super.get(key);
    }

    @Override
    public Integer put(Integer key, Integer value) {
        return super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // return true 的话，如果map容量已满，允许新的插入，并且移除老的数据
        //这里是实现，容量满了以后，最老的数据删除的操作
        return size() > capacity;
    }
}
           

1.时间 O(1)

2.空间 O(capacity)
           

public class LRUCache {

    private int capacity;
    private int size;
    private DoubleListNode startSentinel;
    private DoubleListNode endSentinel;
    private HashMap<Integer, DoubleListNode> hashMap;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        hashMap = new HashMap<>(capacity);
        startSentinel = new DoubleListNode();
        endSentinel = new DoubleListNode();
        startSentinel.next = endSentinel;
        endSentinel.pre = startSentinel;
    }

    class DoubleListNode {
        private Integer key;
        private Integer val;
        private DoubleListNode pre;
        private DoubleListNode next;

        public DoubleListNode() {
        }

        public DoubleListNode(Integer key, Integer val) {
            this.key = key;
            this.val = val;
        }

        @Override
        public String toString() {
            return "val=" + val;
        }
    }

    @Override
    public String toString() {
        return "LRUCache{" +
                "hashMap=" + hashMap +
                '}';
    }




    public Integer get(Integer key) {
        DoubleListNode node = hashMap.get(key);
        //获取不到返回-1
        if (node == null) {
            return -1;
        }
        //移动数据到链表结尾
        moveToTail(node);
        return node.val;
    }

    public void put(Integer key, Integer value) {
        DoubleListNode node = hashMap.get(key);
        if (node == null) {
            //判断当前size 和 capacity 的大小
            if (size < capacity) {
                //size ++
                size++;
                //新增节点
                node = new DoubleListNode(key, value);
                //移动新节点到链表末尾
                addToTail(node);
                hashMap.put(key, node);

            } else {
                //删除头结点
                DoubleListNode rmNode = removeNode(startSentinel.next);
                hashMap.remove(rmNode.key);
                //移动新节点到链表尾部
                DoubleListNode newNode = new DoubleListNode(key, value);
                addToTail(newNode);
                //添加结点到hashmap
                hashMap.put(key,newNode);
            }
        } else {
            //更新值
            node.val = value;
            //放到尾部
            moveToTail(node);
        }
    }


    /**
     * 移动节点到链表尾部
     *
     * @param node
     */
    private void moveToTail(DoubleListNode node) {
        removeNode(node);
        addToTail(node);
    }

    /**
     * 添加结点到双向链表尾部
     *
     * @param node node
     */
    private void addToTail(DoubleListNode node) {
        node.next = endSentinel;
        node.pre = endSentinel.pre;
        endSentinel.pre.next = node;
        endSentinel.pre = node;
    }

    /**
     * 移除节点
     * @param node node
     * @return re
     */
    private DoubleListNode removeNode(DoubleListNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        return node;
    }

}
           

1.时间 O(1)

2.空间 O(capacity)