力扣加加 - 努力做西湖区最好的算法题解
  • introduction
  • 第一章 - 算法专题
    • 数据结构
    • 链表专题
    • 树专题
    • 堆专题(上)
    • 堆专题(下)
    • 二分专题(上)
    • 二分专题(下)
    • 动态规划(重置版)
    • 大话搜索
    • 二叉树的遍历
    • 哈夫曼编码和游程编码
    • 布隆过滤器
    • 前缀树
    • 回溯
    • 滑动窗口(思路 + 模板)
    • 位运算
    • 小岛问题
    • 最大公约数
    • 并查集
    • 平衡二叉树专题
    • 蓄水池抽样
    • 单调栈
  • 第二章 - 91 天学算法
    • 91 天学算法第三期视频会议总结
    • 第一期讲义-二分法
    • 第一期讲义-双指针
    • 第三期正在火热进行中
  • 第三章 - 精选题解
    • 字典序列删除
    • 西法的刷题秘籍】一次搞定前缀和
    • 字节跳动的算法面试题是什么难度?
    • 字节跳动的算法面试题是什么难度?(第二弹)
    • 《我是你的妈妈呀》 * 第一期
    • 一文带你看懂二叉树的序列化
    • 穿上衣服我就不认识你了?来聊聊最长上升子序列
    • 你的衣服我扒了 * 《最长公共子序列》
    • 一文看懂《最大子序列和问题》
  • 第四章 - 高频考题(简单)
    • 面试题 17.12. BiNode
    • 0001. 两数之和
    • 0020. 有效的括号
    • 0021. 合并两个有序链表
    • 0026. 删除排序数组中的重复项
    • 0053. 最大子序和
    • 0160. 相交链表
    • 0066. 加一
    • 0088. 合并两个有序数组
    • 0101. 对称二叉树
    • 0104. 二叉树的最大深度
    • 0108. 将有序数组转换为二叉搜索树
    • 0121. 买卖股票的最佳时机
    • 0122. 买卖股票的最佳时机 II
    • 0125. 验证回文串
    • 0136. 只出现一次的数字
    • 0155. 最小栈
    • 0167. 两数之和 II 输入有序数组
    • 0169. 多数元素
    • 0172. 阶乘后的零
    • 0190. 颠倒二进制位
    • 0191. 位 1 的个数
    • 0198. 打家劫舍
    • 0203. 移除链表元素
    • 0206. 反转链表
    • 0219. 存在重复元素 II
    • 0226. 翻转二叉树
    • 0232. 用栈实现队列
    • 0263. 丑数
    • 0283. 移动零
    • 0342. 4 的幂
    • 0349. 两个数组的交集
    • 0371. 两整数之和
    • 401. 二进制手表
    • 0437. 路径总和 III
    • 0455. 分发饼干
    • 0504. 七进制数
    • 0575. 分糖果
    • 0665. 非递减数列
    • 0661. 图片平滑器
    • 821. 字符的最短距离
    • 0874. 模拟行走机器人
    • 1128. 等价多米诺骨牌对的数量
    • 1260. 二维网格迁移
    • 1332. 删除回文子序列
    • 2591. 将钱分给最多的儿童
  • 第五章 - 高频考题(中等)
    • 面试题 17.09. 第 k 个数
    • 面试题 17.23. 最大黑方阵
    • 面试题 16.16. 部分排序
    • Increasing Digits
    • Longest Contiguously Strictly Increasing Sublist After Deletion
    • Consecutive Wins
    • Number of Substrings with Single Character Difference
    • Bus Fare
    • Minimum Dropping Path Sum
    • Every Sublist Min Sum
    • Maximize the Number of Equivalent Pairs After Swaps
    • 0002. 两数相加
    • 0003. 无重复字符的最长子串
    • 0005. 最长回文子串
    • 0011. 盛最多水的容器
    • 0015. 三数之和
    • 0017. 电话号码的字母组合
    • 0019. 删除链表的倒数第 N 个节点
    • 0022. 括号生成
    • 0024. 两两交换链表中的节点
    • 0029. 两数相除
    • 0031. 下一个排列
    • 0033. 搜索旋转排序数组
    • 0039. 组合总和
    • 0040. 组合总和 II
    • 0046. 全排列
    • 0047. 全排列 II
    • 0048. 旋转图像
    • 0049. 字母异位词分组
    • 0050. Pow(x, n)
    • 0055. 跳跃游戏
    • 0056. 合并区间
    • 0060. 第 k 个排列
    • 0061. 旋转链表
    • 0062. 不同路径
    • 0073. 矩阵置零
    • 0075. 颜色分类
    • 0078. 子集
    • 0079. 单词搜索
    • 0080. 删除排序数组中的重复项 II
    • 0086. 分隔链表
    • 0090. 子集 II
    • 0091. 解码方法
    • 0092. 反转链表 II
    • 0094. 二叉树的中序遍历
    • 0095. 不同的二叉搜索树 II
    • 0096. 不同的二叉搜索树
    • 0098. 验证二叉搜索树
    • 0102. 二叉树的层序遍历
    • 0103. 二叉树的锯齿形层次遍历
    • 0113. 路径总和 II
    • 0129. 求根到叶子节点数字之和
    • 0130. 被围绕的区域
    • 0131. 分割回文串
    • 0139. 单词拆分
    • 0144. 二叉树的前序遍历
    • 0147. 对链表进行插入排序
    • 0150. 逆波兰表达式求值
    • 0152. 乘积最大子数组
    • 0153. 寻找旋转排序数组中的最小值
    • 0199. 二叉树的右视图
    • 0200. 岛屿数量
    • 0201. 数字范围按位与
    • 0208. 实现 Trie (前缀树)
    • 0209. 长度最小的子数组
    • 0211. 添加与搜索单词 - 数据结构设计
    • 0215. 数组中的第 K 个最大元素
    • 0220. 存在重复元素 III
    • 0221. 最大正方形
    • 0227. 基本计算器 II
    • 0229. 求众数 II
    • 0230. 二叉搜索树中第 K 小的元素
    • 0236. 二叉树的最近公共祖先
    • 0238. 除自身以外数组的乘积
    • 0240. 搜索二维矩阵 II
    • 0279. 完全平方数
    • 0309. 最佳买卖股票时机含冷冻期
    • 0322. 零钱兑换
    • 0324. 摆动排序 II
    • 0328. 奇偶链表
    • 0331. 验证二叉树的前序序列化
    • 0334. 递增的三元子序列
    • 0337. 打家劫舍 III
    • 0343. 整数拆分
    • 0365. 水壶问题
    • 0378. 有序矩阵中第 K 小的元素
    • 0380. 常数时间插入、删除和获取随机元素
    • 0394. 字符串解码
    • 0416. 分割等和子集
    • 0424. 替换后的最长重复字符
    • 0438. 找到字符串中所有字母异位词
    • 0445. 两数相加 II
    • 0454. 四数相加 II
    • 0456. 132 模式
    • 0457.457. 环形数组是否存在循环
    • 0464. 我能赢么
    • 0470. 用 Rand7() 实现 Rand10
    • 0473. 火柴拼正方形
    • 0494. 目标和
    • 0516. 最长回文子序列
    • 0513. 找树左下角的值
    • 0518. 零钱兑换 II
    • 0525. 连续数组
    • 0547. 朋友圈
    • 0560. 和为 K 的子数组
    • 0609. 在系统中查找重复文件
    • 0611. 有效三角形的个数
    • 0673. 最长递增子序列的个数
    • 0686. 重复叠加字符串匹配
    • 0710. 黑名单中的随机数
    • 0714. 买卖股票的最佳时机含手续费
    • 0718. 最长重复子数组
    • 0735. 行星碰撞
    • 0754. 到达终点数字
    • 0785. 判断二分图
    • 0790. 多米诺和托米诺平铺
    • 0799. 香槟塔
    • 0801. 使序列递增的最小交换次数
    • 0816. 模糊坐标
    • 0820. 单词的压缩编码
    • 0838. 推多米诺
    • 0873. 最长的斐波那契子序列的长度
    • 0875. 爱吃香蕉的珂珂
    • 0877. 石子游戏
    • 0886. 可能的二分法
    • 0898. 子数组按位或操作
    • 0900. RLE 迭代器
    • 0911. 在线选举
    • 0912. 排序数组
    • 0932. 漂亮数组
    • 0935. 骑士拨号器
    • 0947. 移除最多的同行或同列石头
    • 0959. 由斜杠划分区域
    • 0978. 最长湍流子数组
    • 0987. 二叉树的垂序遍历
    • 1004. 最大连续 1 的个数 III
    • 1011. 在 D 天内送达包裹的能力
    • 1014. 最佳观光组合
    • 1015. 可被 K 整除的最小整数
    • 1019. 链表中的下一个更大节点
    • 1020. 飞地的数量
    • 1023. 驼峰式匹配
    • 1031. 两个非重叠子数组的最大和
    • 1043. 分隔数组以得到最大和
    • 1053. 交换一次的先前排列)
    • 1104. 二叉树寻路
    • 1129. 颜色交替的最短路径
    • 1131.绝对值表达式的最大值
    • 1138. 字母板上的路径
    • 1186. 删除一次得到子数组最大和
    • 1218. 最长定差子序列
    • 1227. 飞机座位分配概率
    • 1261. 在受污染的二叉树中查找元素
    • 1262. 可被三整除的最大和
    • 1297. 子串的最大出现次数
    • 1310. 子数组异或查询
    • 1334. 阈值距离内邻居最少的城市
    • 1371.每个元音包含偶数次的最长子字符串
    • 1381. 设计一个支持增量操作的栈
    • 1438. 绝对差不超过限制的最长连续子数组
    • 1558. 得到目标数组的最少函数调用次数
    • 1574. 删除最短的子数组使剩余数组有序
    • 1631. 最小体力消耗路径
    • 1638. 统计只差一个字符的子串数目
    • 1658. 将 x 减到 0 的最小操作数
    • 1697. 检查边长度限制的路径是否存在
    • 1737. 满足三条件之一需改变的最少字符数
    • 1770. 执行乘法运算的最大分数
    • 1793. 好子数组的最大分数
    • 1834. 单线程 CPU
    • 1899. 合并若干三元组以形成目标三元组
    • 1904. 你完成的完整对局数
    • 1906. 查询差绝对值的最小值
    • 1906. 查询差绝对值的最小值
    • 2007. 从双倍数组中还原原数组
    • 2008. 出租车的最大盈利
    • 2100. 适合打劫银行的日子
    • 2101. 引爆最多的炸弹
    • 2121. 相同元素的间隔之和
    • 2207. 字符串中最多数目的子字符串
    • 2592. 最大化数组的伟大值
    • 2593. 标记所有元素后数组的分数
    • 2817. 限制条件下元素之间的最小绝对差
    • 2865. 美丽塔 I
    • 2866. 美丽塔 II
    • 2939. 最大异或乘积
    • 3377. 使两个整数相等的数位操作
    • 3404. 统计特殊子序列的数目
    • 3428. 至多 K 个子序列的最大和最小和
  • 第六章 - 高频考题(困难)
    • LCP 20. 快速公交
    • LCP 21. 追逐游戏
    • Number Stream to Intervals
    • Triple-Inversion
    • Kth-Pair-Distance
    • Minimum-Light-Radius
    • Largest Equivalent Set of Pairs
    • Ticket-Order.md
    • Connected-Road-to-Destination
    • 0004. 寻找两个正序数组的中位数
    • 0023. 合并 K 个升序链表
    • 0025. K 个一组翻转链表
    • 0030. 串联所有单词的子串
    • 0032. 最长有效括号
    • 0042. 接雨水
    • 0052. N 皇后 II
    • 0057. 插入区间
    • 0065. 有效数字
    • 0084. 柱状图中最大的矩形
    • 0085. 最大矩形
    • 0087. 扰乱字符串
    • 0124. 二叉树中的最大路径和
    • 0128. 最长连续序列
    • 0132. 分割回文串 II
    • 0140. 单词拆分 II
    • 0145. 二叉树的后序遍历
    • 0146. LRU 缓存机制
    • 0154. 寻找旋转排序数组中的最小值 II
    • 0212. 单词搜索 II
    • 0239. 滑动窗口最大值
    • 0295. 数据流的中位数
    • 0297. 二叉树的序列化与反序列化
    • 0301. 删除无效的括号
    • 0312. 戳气球
    • 330. 按要求补齐数组
    • 0335. 路径交叉
    • 0460. LFU 缓存
    • 0472. 连接词
    • 0480. 滑动窗口中位数
    • 0483. 最小好进制
    • 0488. 祖玛游戏
    • 0493. 翻转对
    • 0664. 奇怪的打印机
    • 0679. 24 点游戏
    • 0715. Range 模块
    • 0726. 原子的数量
    • 0768. 最多能完成排序的块 II
    • 0805. 数组的均值分割
    • 0839. 相似字符串组
    • 0887. 鸡蛋掉落
    • 0895. 最大频率栈
    • 0975. 奇偶跳
    • 0995. K 连续位的最小翻转次数
    • 1032. 字符流
    • 1168. 水资源分配优化
    • 1178. 猜字谜
    • 1203. 项目管理
    • 1255. 得分最高的单词集合
    • 1345. 跳跃游戏 IV
    • 1449. 数位成本和为目标值的最大数字
    • 1494. 并行课程 II
    • 1521. 找到最接近目标值的函数值
    • 1526. 形成目标数组的子数组最少增加次数
    • 1639. 通过给定词典构造目标字符串的方案数
    • 1649. 通过指令创建有序数组
    • 1671. 得到山形数组的最少删除次数
    • 1707. 与数组中元素的最大异或值
    • 1713. 得到子序列的最少操作次数
    • 1723. 完成所有工作的最短时间
    • 1787. 使所有区间的异或结果为零
    • 1835. 所有数对按位与结果的异或和
    • 1871. 跳跃游戏 VII
    • 1872. 石子游戏 VIII
    • 1883. 准时抵达会议现场的最小跳过休息次数
    • 1970. 你能穿过矩阵的最后一天
    • 2009. 使数组连续的最少操作数
    • 2025. 分割数组的最多方案数
    • 2030. 含特定字母的最小子序列
    • 2102. 序列顺序查询
    • 2141. 同时运行 N 台电脑的最长时间
    • 2179. 统计数组中好三元组数目 👍
    • 2209. 用地毯覆盖后的最少白色砖块
    • 2281.sum-of-total-strength-of-wizards
    • 2306. 公司命名
    • 2312. 卖木头块
    • 2842. 统计一个字符串的 k 子序列美丽值最大的数目
    • 2972. 统计移除递增子数组的数目 II
    • 3027. 人员站位的方案数 II
    • 3041. 修改数组后最大化数组中的连续元素数目
    • 3082. 求出所有子序列的能量和
    • 3108. 带权图里旅途的最小代价
    • 3347. 执行操作后元素的最高频率 II
    • 3336. 最大公约数相等的子序列数量
    • 3410. 删除所有值为某个元素后的最大子数组和
  • 后序
由 GitBook 提供支持
在本页
  • 题目地址(146. LRU 缓存机制)
  • 题目描述
  • 代码

这有帮助吗?

  1. 第六章 - 高频考题(困难)

0146. LRU 缓存机制

题目地址(146. LRU 缓存机制)

https://leetcode-cn.com/problems/lru-cache/

题目描述

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

实现 LRUCache 类:

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

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

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

进阶:你是否可以在 O(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);    // 返回 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. 确定需要使用的数据结构

    1. 根据题目要求,存储的数据需要保证顺序关系(逻辑层面) ===> 使用数组,链表等保证顺序关系

    2. 同时需要对数据进行频繁的增删, 时间复杂度 O(1) ==> 使用链表等

    3. 对数据进行读取时, 时间复杂度 O(1) ===> 使用哈希表 最终采取双向链表 + 哈希表

      1. 双向链表按最后一次访问的时间的顺序进行排列, 链表头部为最近访问的节点

      2. 哈希表,以关键字为键,以链表节点的地址为值

  2. put 操作 通过哈希表, 查看传入的关键字对应的链表节点, 是否存在

    1. 如果存在,

      1. 将该链表节点的值更新

      2. 将该该链表节点调整至链表头部

    2. 如果不存在

      1. 如果链表容量未满,

        1. 新生成节点,

        2. 将该节点位置调整至链表头部

      2. 如果链表容量已满

        1. 删除尾部节点

        2. 新生成节点

        3. 将该节点位置调整至链表头部

      3. 将新生成的节点,按关键字为键,节点地址为值插入哈希表

  3. get 操作 通过哈希表, 查看传入的关键字对应的链表节点, 是否存在

    1. 节点存在

      1. 将该节点位置调整至链表头部

      2. 返回该节点的值

    2. 节点不存在, 返回 null

伪代码如下:

var LRUCache = function(capacity) {
	保存一个该数据结构的最大容量
	生成一个双向链表,同时保存该链表的头结点与尾节点
	生成一个哈希表
};

function get (key) {
	if 哈希表中存在该关键字 {
		根据哈希表获取该链表节点
		将该节点放置于链表头部
		return 链表节点的值
	} else {
		  return -1
	}
};

function put (key, value) {
    if 哈希表中存在该关键字 {
		根据哈希表获取该链表节点
		将该链表节点的值更新
		将该节点放置于链表头部
	} else {
		if 容量已满 {
			删除链表尾部的节点
			新生成一个节点
			将该节点放置于链表头部
		} else {
			新生成一个节点
			将该节点放置于链表头部
		}
	}
};

代码

语言支持: JS, Go, PHP, Python3

JS Code:

class ListNode{
    constructor(key, val){
        this.key = key;
        this.val = val;
        this.pre = null;
        this.next = null;
    }
};

class LRUCache{
    constructor(capacity){
        this.capacity = capacity;
        this.size = 0;
        this.data = {};
        this.head = new ListNode();
        this.tail = new ListNode();
        this.head.next = this.tail;
        this.tail.pre = this.head;
    }

    get(key){
        if(!this.data[key]) return -1;
        else{
            let node = this.data[key];
            this.removeNode(node);
            this.appendHead(node);
            
            return node.val;
        }
    }

    put(key, value){
        if(!this.data[key]){
            let node = new ListNode(key, value);

            this.data[key] = node;
            this.appendHead(node);
            this.size++;

            if(this.size > this.capacity){
                const lastKey = this.removeTail();
                delete this.data[lastKey];
                this.size--;
            }

        }else{
            let node = this.data[key];
            this.removeNode(node);
            node.val = value;
            this.appendHead(node);
        }   
    }

    removeNode(node){
        let preNode = node.pre;
        let nextNode = node.next;

        preNode.next = nextNode;
        nextNode.pre = preNode;
    }

    appendHead(node){
        let firstNode = this.head.next;

        this.head.next = node;
        node.pre = this.head;
        node.next = firstNode;
        firstNode.pre = node;
    }

    removeTail(){
        let key = this.tail.pre.key;

        this.removeNode(this.tail.pre);
        
        return key;
    }
}

Go Code:

type LRUCache struct {
	Cap   int
	Hash  map[int]*DoubleListNode
	Cache *DoubleList
	Size  int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		Cap:   capacity,
		Hash:  make(map[int]*DoubleListNode),
		Cache: NewDoubleList(),
	}
}

func (this *LRUCache) Get(key int) int {
	n, ok := this.Hash[key]
	if !ok {
		return -1
	}

	// 设为最近使用过
	this.Cache.remove(n)
	this.Cache.append(n)

	return n.Val
}

func (this *LRUCache) Put(key int, value int) {
	n, ok := this.Hash[key]
	if !ok { // cache 不存在
		// 增加节点
		newNode := &DoubleListNode{Key: key, Val: value}
		this.Hash[key] = newNode
		this.Cache.append(newNode)

		if this.Cap == this.Size { // 已满
			// 删除尾节点
			tailNode := this.Cache.tail.Pre
			delete(this.Hash, tailNode.Key)
			this.Cache.remove(tailNode)
		} else {
			this.Size++
		}
	} else {
		// cache 存在
		// 设为最近使用过
		this.Cache.remove(n)
        this.Cache.append(n)

        n.Val = value // 更新值
	}
}

type DoubleListNode struct {
	Key, Val  int
	Pre, Next *DoubleListNode
}

type DoubleList struct {
	Head, tail *DoubleListNode
}

func NewDoubleList() *DoubleList {
	dl := &DoubleList{
		Head: &DoubleListNode{},
		tail: &DoubleListNode{},
	}
	dl.Head.Next = dl.tail
	dl.tail.Pre = dl.Head
	return dl
}

func (dl *DoubleList) append(n *DoubleListNode) {
	n.Next = dl.Head.Next
	n.Pre = dl.Head
	dl.Head.Next.Pre = n
	dl.Head.Next = n
}

func (dl *DoubleList) remove(n *DoubleListNode) {
	n.Pre.Next = n.Next
	n.Next.Pre = n.Pre
}

PHP Code:

class LRUCache
{
    public $hash = []; // key => DoubleListNode
    public $cache;
    public $size = 0;
    public $cap; // 容量

    /**
     * @param Integer $capacity
     */
    function __construct($capacity)
    {
        $this->cap = $capacity;
        $this->cache = new DoubleList();
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key)
    {
        if (!isset($this->hash[$key])) return -1;

        // 更新节点
        /** @var DoubleListNode $node */
        $node = $this->hash[$key];
        $this->cache->remove($node);
        $this->cache->append($node);

        return $node->val;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value)
    {
        if (isset($this->hash[$key])) { // key 存在
            // 更新节点
            /** @var DoubleListNode $node */
            $node = $this->hash[$key];
            $this->cache->remove($node);
            $this->cache->append($node);
            $node->val = $value;
        } else { // key 不存在, 新增节点
            $node = new DoubleListNode($key, $value);
            $this->cache->append($node);
            $this->hash[$key] = $node;

            if ($this->size == $this->cap) {
                // 删除原节点
                $oldNode = $this->cache->tail->pre;
                $this->cache->remove($oldNode);
                unset($this->hash[$oldNode->key]);
            } else {
                $this->size++;
            }
        }
    }
}

class DoubleListNode
{
    public $key;
    public $val;
    public $pre;
    public $next;

    public function __construct($key = null, $val = null)
    {
        if ($key) $this->key = $key;
        if ($val) $this->val = $val;
    }
}

class DoubleList
{
    public $head;
    public $tail;

    public function __construct()
    {
        $this->head = new DoubleListNode();
        $this->tail = new DoubleListNode();
        $this->head->next = $this->tail;
        $this->tail->pre = $this->head;
    }

    public function append(DoubleListNode $node)
    {
        $node->pre = $this->head;
        $node->next = $this->head->next;
        $this->head->next->pre = $node;
        $this->head->next = $node;
    }

    public function remove(DoubleListNode $node)
    {
        $node->pre->next = $node->next;
        $node->next->pre = $node->pre;
    }
}

Python Code:

来自 leetcode

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()
        # 使用伪头部和伪尾部节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 如果 key 存在,先通过哈希表定位,再移到头部
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 如果 key 不存在,创建一个新的节点
            node = DLinkedNode(key, value)
            # 添加进哈希表
            self.cache[key] = node
            # 添加至双向链表的头部
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                # 如果超出容量,删除双向链表的尾部节点
                removed = self.removeTail()
                # 删除哈希表中对应的项
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            # 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

复杂度分析

  • 时间复杂度:$O(1)$

  • 空间复杂度:$O(n)$ n 为容量的大小

上一页0145. 二叉树的后序遍历下一页0154. 寻找旋转排序数组中的最小值 II

最后更新于3年前

这有帮助吗?