前言🌧️
算法，对前端人来说陌生又熟悉，很多时候我们都不会像后端工程师一样重视这项能力。但事实上，算法对每一个程序员来说，都有着不可撼动的地位。
因为开发的过程就是把实际问题转换成计算机可识别的指令，也就是《数据结构》里说的，「设计出数据结构，在施加以算法就行了」。
当然，学习也是有侧重点的，作为前端我们不需要像后端开发一样对算法全盘掌握，有些比较偏、不实用的类型和解法，只要稍做了解即可。
题目🦀
146. 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，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 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 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
解题思路🌵
- 使用map来存储缓存
- 此题可以和
vue3源码中的KeepAlive关联
解题步骤🐂
- 创建map来保存数据
- get：访问某key，访问完要将其放在最后的。若key存在，先保存value值，删除key，再添加key，最后返回保存的value值。若key不存在，返回-1
- put：新加一个key，要将其放在最后的。所以，若key已经存在，先删除，再添加。如果容量超出范围了，将map中的头部删除。
源码🔥
/** * @param {number} capacity */ var LRUCache = function(capacity) { this.cache=new Map() this.max=capacity }; /** * @param {number} key * @return {number} */ LRUCache.prototype.get = function(key) { if(this.cache.has(key)){ const temp = this.cache.get(key) this.cache.delete(key) this.cache.set(key,temp) return this.cache.get(key) }else{ return -1 } }; /** * @param {number} key * @param {number} value * @return {void} */ LRUCache.prototype.put = function(key, value) { if(this.cache.has(key)){ this.cache.delete(key) this.cache.set(key,value) }else{ if(this.cache.size>=this.max){ //大于最大缓存容量了，就要考虑清除策略 this.cache.delete(this.cache.keys().next().value) this.cache.set(key,value) }else{ this.cache.set(key,value) } } }; /** * Your LRUCache object will be instantiated and called as such: * var obj = new LRUCache(capacity) * var param_1 = obj.get(key) * obj.put(key,value) */
结束语🌞
那么鱼鱼的LeetCode算法篇的「LeetCode」146-LRU缓存⚡️就结束了，算法这个东西没有捷径，只能多写多练，多总结，文章的目的其实很简单，就是督促自己去完成算法练习并总结和输出，菜不菜不重要，但是热爱🔥，喜欢大家能够喜欢我的短文，也希望通过文章认识更多志同道合的朋友，如果你也喜欢折腾，欢迎加我好友，一起沙雕，一起进步。
