设计并实现一个满足LRU约束的数据结构
题目
请你设计并实现一个满足 「lru (最近最少使用) 缓存」 约束的数据结构。
实现 lrucache 类：
lrucache(int capacity) 以 「正整数」 作为容量 capacity 初始化 lru 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 「逐出」 最久未使用的关键字。
示例：
输入[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提示：
题解（哈希表 + 双向链表）
解题之前先了解一下什么是 「lru缓存」 ， lru 的英文全称为 latest recently used，即 「最近最少使用」 。在缓存占满的时候，先删除最旧的数据。
java 代码实现class lrucache { private int capacity; private map cache; // 保护节点，protecthead.next 为head节点, protecttail.pre为tail节点 private listnode protecthead = new listnode(); private listnode protecttail = new listnode(); public lrucache(int capacity) { this.capacity = capacity; cache = new hashmap(capacity); protecthead.next = protecttail; protecttail.pre = protecthead; } // 删除指定节点 private void remove(listnode listnode){ listnode.pre.next = listnode.next; listnode.next.pre = listnode.pre; listnode.pre = null; listnode.next = null; } // 添加到末尾 private void addtotail(listnode listnode){ protecttail.pre.next = listnode; listnode.pre = protecttail.pre; listnode.next = protecttail; protecttail.pre = listnode; } // 从当前位置移动到末尾 private void movetotail(listnode listnode){ this.remove(listnode); this.addtotail(listnode); } public int get(int key) { if(cache.containskey(key)){ listnode listnode = cache.get(key); this.movetotail(listnode); return listnode.value; }else{ return -1; } } public void put(int key, int value) { if(cache.containskey(key)){ // 将 key 移动到最新的位置 // 1. 在旧的位置删除 // 2. 追加key到链表末尾 listnode listnode = cache.get(key); // 这里必须重新赋值，虽然缓冲已经存在了，但是可能值不一样。 listnode.value = value; this.movetotail(listnode); return; } if(cache.size() == capacity){ // 1. 找到最旧的数据，也就是链表的head，删除head // 2. 在cache map 中删除 head对应的key listnode headnode = protecthead.next; this.remove(headnode); cache.remove(headnode.key); } // 1. 添加新的key到cache map // 2. 追加新的key到链表末尾 listnode listnode = new listnode(); listnode.key = key; listnode.value = value; this.addtotail(listnode); cache.put(key, listnode); }}class listnode{ int key; int value; listnode pre; listnode next;}go 代码实现// 定义双向链表type mylistnode struct { key, value int pre, next *mylistnode}type lrucache struct { size, capacity int cache map[int]*mylistnode protecthead, protecttail *mylistnode}func constructor(capacity int) lrucache { lrucache := lrucache{ size: 0, capacity: capacity, cache: map[int]*mylistnode{}, protecthead: &mylistnode{}, protecttail: &mylistnode{}, } lrucache.protecthead.next = lrucache.protecttail lrucache.protecttail.pre = lrucache.protecthead return lrucache}func (this *lrucache) get(key int) int { if listnode, ok := this.cache[key]; ok { this.movetotail(listnode); return listnode.value; }else{ return -1 }}func (this *lrucache) put(key int, value int) { if listnode, ok := this.cache[key]; ok { listnode.value = value; this.movetotail(listnode); return; } if(this.size == this.capacity){ headnode := this.protecthead.next; this.remove(headnode); delete(this.cache, headnode.key); this.size-- } listnode := &mylistnode{ key: key, value: value, } this.addtotail(listnode) this.cache[key] = listnode this.size++}// 删除指定节点func (this *lrucache) remove(listnode *mylistnode){ listnode.pre.next = listnode.next; listnode.next.pre = listnode.pre; listnode.pre = nil; listnode.next = nil;}// 添加到末尾func (this *lrucache) addtotail(listnode *mylistnode){ this.protecttail.pre.next = listnode listnode.pre = this.protecttail.pre listnode.next = this.protecttail this.protecttail.pre = listnode}// 从当前位置移动到末尾func (this *lrucache) movetotail(listnode *mylistnode){ this.remove(listnode); this.addtotail(listnode);}复杂度分析
云母电容的用途_云母电容特点
智慧城市的必然之选是什么
韩国半导体制造商开始在中国寻求替代厂家寻求“突围”
Linux MIPI CSI开发指南
采用东芝DTMOSIV超级结MOSFET来解决这些问题
设计并实现一个满足LRU约束的数据结构
MYSQL中读写分离有什么作用及基本架构说明
Dialog快速充电技术首度商用 支援华为专属协定
高效提升控制效率 | 基于ACM32 MCU的LED灯箱控制器方案
西井科技在TOC欧洲展重磅发布“新一代港口数智化运营平台”
机器人外壳与底盘是制约现阶段市场化发展的关键要素
蓝牙耳机品牌，高音质蓝牙耳机分享，学生党听音乐平价蓝牙耳机
车企向国内市场输出新能源汽车 将会带来一连串的麻烦
荣耀V9play评测 体验上与高端机还是存在差距的
机器人焊机和普通焊机的主要有哪些区别？
一文了解圣邦微电子逻辑芯片全貌
架空线入地、合杆整治……这些道路焕然一新！
基于I2C总线的高分辨率红外式触摸屏设计
AMD 7nm U/H系列处理器支持面容和指纹登陆
关于砷化镓晶片的湿式化学蚀刻的研究报告
请你设计并实现一个满足 「lru (最近最少使用) 缓存」 约束的数据结构。
实现 lrucache 类：
lrucache(int capacity) 以 「正整数」 作为容量 capacity 初始化 lru 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 「逐出」 最久未使用的关键字。
示例：
输入[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提示：
题解（哈希表 + 双向链表）
解题之前先了解一下什么是 「lru缓存」 ， lru 的英文全称为 latest recently used，即 「最近最少使用」 。在缓存占满的时候，先删除最旧的数据。
java 代码实现class lrucache { private int capacity; private map cache; // 保护节点，protecthead.next 为head节点, protecttail.pre为tail节点 private listnode protecthead = new listnode(); private listnode protecttail = new listnode(); public lrucache(int capacity) { this.capacity = capacity; cache = new hashmap(capacity); protecthead.next = protecttail; protecttail.pre = protecthead; } // 删除指定节点 private void remove(listnode listnode){ listnode.pre.next = listnode.next; listnode.next.pre = listnode.pre; listnode.pre = null; listnode.next = null; } // 添加到末尾 private void addtotail(listnode listnode){ protecttail.pre.next = listnode; listnode.pre = protecttail.pre; listnode.next = protecttail; protecttail.pre = listnode; } // 从当前位置移动到末尾 private void movetotail(listnode listnode){ this.remove(listnode); this.addtotail(listnode); } public int get(int key) { if(cache.containskey(key)){ listnode listnode = cache.get(key); this.movetotail(listnode); return listnode.value; }else{ return -1; } } public void put(int key, int value) { if(cache.containskey(key)){ // 将 key 移动到最新的位置 // 1. 在旧的位置删除 // 2. 追加key到链表末尾 listnode listnode = cache.get(key); // 这里必须重新赋值，虽然缓冲已经存在了，但是可能值不一样。 listnode.value = value; this.movetotail(listnode); return; } if(cache.size() == capacity){ // 1. 找到最旧的数据，也就是链表的head，删除head // 2. 在cache map 中删除 head对应的key listnode headnode = protecthead.next; this.remove(headnode); cache.remove(headnode.key); } // 1. 添加新的key到cache map // 2. 追加新的key到链表末尾 listnode listnode = new listnode(); listnode.key = key; listnode.value = value; this.addtotail(listnode); cache.put(key, listnode); }}class listnode{ int key; int value; listnode pre; listnode next;}go 代码实现// 定义双向链表type mylistnode struct { key, value int pre, next *mylistnode}type lrucache struct { size, capacity int cache map[int]*mylistnode protecthead, protecttail *mylistnode}func constructor(capacity int) lrucache { lrucache := lrucache{ size: 0, capacity: capacity, cache: map[int]*mylistnode{}, protecthead: &mylistnode{}, protecttail: &mylistnode{}, } lrucache.protecthead.next = lrucache.protecttail lrucache.protecttail.pre = lrucache.protecthead return lrucache}func (this *lrucache) get(key int) int { if listnode, ok := this.cache[key]; ok { this.movetotail(listnode); return listnode.value; }else{ return -1 }}func (this *lrucache) put(key int, value int) { if listnode, ok := this.cache[key]; ok { listnode.value = value; this.movetotail(listnode); return; } if(this.size == this.capacity){ headnode := this.protecthead.next; this.remove(headnode); delete(this.cache, headnode.key); this.size-- } listnode := &mylistnode{ key: key, value: value, } this.addtotail(listnode) this.cache[key] = listnode this.size++}// 删除指定节点func (this *lrucache) remove(listnode *mylistnode){ listnode.pre.next = listnode.next; listnode.next.pre = listnode.pre; listnode.pre = nil; listnode.next = nil;}// 添加到末尾func (this *lrucache) addtotail(listnode *mylistnode){ this.protecttail.pre.next = listnode listnode.pre = this.protecttail.pre listnode.next = this.protecttail this.protecttail.pre = listnode}// 从当前位置移动到末尾func (this *lrucache) movetotail(listnode *mylistnode){ this.remove(listnode); this.addtotail(listnode);}复杂度分析
云母电容的用途_云母电容特点
智慧城市的必然之选是什么
韩国半导体制造商开始在中国寻求替代厂家寻求“突围”
Linux MIPI CSI开发指南
采用东芝DTMOSIV超级结MOSFET来解决这些问题
设计并实现一个满足LRU约束的数据结构
MYSQL中读写分离有什么作用及基本架构说明
Dialog快速充电技术首度商用 支援华为专属协定
高效提升控制效率 | 基于ACM32 MCU的LED灯箱控制器方案
西井科技在TOC欧洲展重磅发布“新一代港口数智化运营平台”
机器人外壳与底盘是制约现阶段市场化发展的关键要素
蓝牙耳机品牌，高音质蓝牙耳机分享，学生党听音乐平价蓝牙耳机
车企向国内市场输出新能源汽车 将会带来一连串的麻烦
荣耀V9play评测 体验上与高端机还是存在差距的
机器人焊机和普通焊机的主要有哪些区别？
一文了解圣邦微电子逻辑芯片全貌
架空线入地、合杆整治……这些道路焕然一新！
基于I2C总线的高分辨率红外式触摸屏设计
AMD 7nm U/H系列处理器支持面容和指纹登陆
关于砷化镓晶片的湿式化学蚀刻的研究报告