DeepSeek    LeetCode 146. LRU 缓存 Python3实现
LeetCode 146. LRU 缓存 - Python3 实现题目要求设计一个满足 LRU最近最少使用 策略的缓存类· get(key)如果 key 存在返回 value否则返回 -1。· put(key, value)如果 key 存在更新 value如果不存在插入。若超出容量则删除最久未使用的 key。· 要求 get 和 put 时间复杂度均为 O(1)。方法一使用 OrderedDict简洁版Python 的 collections.OrderedDict 天然支持按插入顺序排列并提供了 move_to_end 和 popitem(lastFalse) 方法非常适合实现 LRU。fromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity:int):self.capacitycapacity self.cacheOrderedDict()defget(self,key:int)-int:ifkeynotinself.cache:return-1# 将访问过的 key 移到末尾表示最近使用self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)-None:ifkeyinself.cache:# 已存在先移到末尾再更新值self.cache.move_to_end(key)self.cache[key]value# 超出容量删除最久未使用的即字典开头的元素iflen(self.cache)self.capacity:self.cache.popitem(lastFalse)方法二哈希表 双向链表面试推荐手写为了彻底理解 LRU 的底层原理建议手写一个双向链表 字典的实现。classNode:__slots__(key,value,prev,next)def__init__(self,key0,value0):self.keykey self.valuevalue self.prevNoneself.nextNoneclassLRUCache:def__init__(self,capacity:int):self.capacitycapacity self.cache{}# key - Nodeself.size0# 使用伪头尾节点方便操作self.headNode()self.tailNode()self.head.nextself.tail self.tail.prevself.headdef_add_to_head(self,node:Node)-None:将节点添加到头部最近使用node.prevself.head node.nextself.head.nextself.head.next.prevnode self.head.nextnodedef_remove_node(self,node:Node)-None:从链表中移除节点node.prev.nextnode.nextnode.next.prevnode.prevdef_move_to_head(self,node:Node)-None:将节点移动到头部self._remove_node(node)self._add_to_head(node)def_remove_tail(self)-Node:移除尾部节点最久未使用并返回nodeself.tail.prev self._remove_node(node)returnnodedefget(self,key:int)-int:ifkeynotinself.cache:return-1nodeself.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)-None:ifkeyinself.cache:nodeself.cache[key]node.valuevalue self._move_to_head(node)else:nodeNode(key,value)self.cache[key]node self._add_to_head(node)self.size1ifself.sizeself.capacity:removedself._remove_tail()delself.cache[removed.key]self.size-1复杂度分析操作 时间复杂度 空间复杂度get O(1) O(capacity)put O(1) O(capacity)· 哈希表保证查找 O(1)。· 双向链表保证插入、删除、移动节点 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]lruLRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))# 返回 1lru.put(3,3)# 该操作会使得 key 2 被淘汰print(lru.get(2))# 返回 -1lru.put(4,4)# 该操作会使得 key 1 被淘汰print(lru.get(1))# 返回 -1print(lru.get(3))# 返回 3print(lru.get(4))# 返回 4以上两种实现均可通过 LeetCode 146方法一代码简洁方法二更能体现 LRU 的设计思想。

相关新闻

DeepSeek    LeetCode 146. LRU 缓存 C++实现

DeepSeek LeetCode 146. LRU 缓存 C++实现

#include <unordered_map> #include <list>class LRUCache { private:int cap;// 链表头部是最近使用&#xff0c;尾部是最久未使用std::list<std::pair<int, int>> cache; // {key, value}std::unordered_map<int, std::list<std::pair<int,…

2026/11/16 19:28:03 阅读更多 →
二分查找:原理、实现与实战

二分查找:原理、实现与实战

1. 什么是二分查找二分查找&#xff08;Binary Search&#xff09;是一种在有序数组中查找目标元素的高效算法。它的核心思想是每次将查找区间缩小一半&#xff0c;通过不断比较中间元素与目标值的大小关系&#xff0c;快速定位目标位置。大家都知道指数爆炸是吧&#xff0c;但…

2026/11/7 7:17:14 阅读更多 →
第31篇:3DTiles加载——await 那一行之后,城还没来

第31篇:3DTiles加载——await 那一行之后,城还没来

上次我们把整个场景重新渲染了一遍,只为在水面上换出一片倒影。这次换个方向——不再自己造东西,而是把别人已经建好的一整座城,搬进我们的地球里。 搬一座城进来要几行代码?严格说,一行: const tileset = await Cesium3DTileset.fromUrl(url)再 scene.primitives.add(…

2026/11/7 13:00:53 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/16 8:22:12 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/16 8:22:12 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻