*打卡算法*LeetCode 146. LRU 缓存 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。”

题目链接：

来源：力扣（LeetCode）

链接： 146. LRU 缓存 - 力扣（LeetCode）

2、题目描述

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例 1：输入["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);    // 返回 1lRUCache.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);    // 返回 3lRUCache.get(4);    // 返回 4

示例 2：

二、解题

1、思路分析

这道题的主要解法就是用一个哈希表加一个双向链表来实现。

在Python语言中有一种结合了哈希表和双向链表的数据结构OrderedDict
在Java语言中有同样的数据结构LinkedHashMap。

接下来就来实现哈希表加双向链表实现LRU缓存机制。

2、代码实现

代码参考：

public class LRUCache {    class DLinkedNode {        int key;        int value;        DLinkedNode prev;        DLinkedNode next;        public DLinkedNode() {}        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}    }    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();    private int size;    private int capacity;    private DLinkedNode head, tail;    public LRUCache(int capacity) {        this.size = 0;        this.capacity = capacity;        // 使用伪头部和伪尾部节点        head = new DLinkedNode();        tail = new DLinkedNode();        head.next = tail;        tail.prev = head;    }    public int get(int key) {        DLinkedNode node = cache.get(key);        if (node == null) {            return -1;        }        // 如果 key 存在，先通过哈希表定位，再移到头部        moveToHead(node);        return node.value;    }    public void put(int key, int value) {        DLinkedNode node = cache.get(key);        if (node == null) {            // 如果 key 不存在，创建一个新的节点            DLinkedNode newNode = new DLinkedNode(key, value);            // 添加进哈希表            cache.put(key, newNode);            // 添加至双向链表的头部            addToHead(newNode);            ++size;            if (size > capacity) {                // 如果超出容量，删除双向链表的尾部节点                DLinkedNode tail = removeTail();                // 删除哈希表中对应的项                cache.remove(tail.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;    }}

3、时间复杂度

时间复杂度：O(1)

对于put和get的时间复杂度都是O(1)。

空间复杂度：O(capacity)

因为哈希表和双向链表最多存储capacity+1个元素。

三、总结

使用哈希表和双向链表来实现LRU缓存机制：

• 双向链表按照被使用的顺序存储了键值对，靠近头部的键值对是最近使用的
• 哈希表通过缓存数据的键值对映射到其在双向链表中的位置。