题目地址
https://leetcode.com/problems/lru-cache/description/
题目描述
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
思路
由于是保留是最近使用的N条数据,这就和队列的特性很符合, 先进入队列的,先出队列。
因此思路就是用一个队列来记录目前缓存的所有key, 每次push都进行判断,如果
超出最大容量限制则进行清除缓存的操作, 具体清除谁就按照刚才说的队列方式进行处理,同时对key进行入队操作。
get的时候,如果缓存中有,则调整队列(具体操作为删除指定元素和入队两个操作)。 缓存中没有则返回-1
关键点解析
-
队列简化操作
-
队列的操作是这道题的灵魂, 很容易少考虑情况
代码
/* * @lc app=leetcode id=146 lang=javascript * * [146] LRU Cache * * https://leetcode.com/problems/lru-cache/description/ * * algorithms * Hard (24.17%) * Total Accepted: 272.8K * Total Submissions: 1.1M * Testcase Example: '["LRUCache","put","put","get","put","get","put","get","get","get"]\n[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]' * * * Design and implement a data structure for Least Recently Used (LRU) cache. * It should support the following operations: get and put. * * * * get(key) - Get the value (will always be positive) of the key if the key * exists in the cache, otherwise return -1. * put(key, value) - Set or insert the value if the key is not already present. * When the cache reached its capacity, it should invalidate the least recently * used item before inserting a new item. * * * Follow up: * Could you do both operations in O(1) time complexity? * * Example: * * LRUCache cache = new LRUCache( 2 ); * * cache.put(1, 1); * cache.put(2, 2); * cache.get(1); // returns 1 * cache.put(3, 3); // evicts key 2 * cache.get(2); // returns -1 (not found) * cache.put(4, 4); // evicts key 1 * cache.get(1); // returns -1 (not found) * cache.get(3); // returns 3 * cache.get(4); // returns 4 * * */ /** * @param {number} capacity */ var LRUCache = function(capacity) { this.cache = {}; this.capacity = capacity; this.size = 0; this.queue = []; }; /** * @param {number} key * @return {number} */ LRUCache.prototype.get = function(key) { const hit = this.cache[key]; if (hit !== undefined) { this.queue = this.queue.filter(q => q !== key); this.queue.push(key); return hit; } return -1; }; /** * @param {number} key * @param {number} value * @return {void} */ LRUCache.prototype.put = function(key, value) { const hit = this.cache[key]; // update cache this.cache[key] = value; if (!hit) { // invalid cache and resize size; if (this.size === this.capacity) { // invalid cache const key = this.queue.shift(); this.cache[key] = undefined; } else { this.size = this.size + 1; } this.queue.push(key); } else { this.queue = this.queue.filter(q => q !== key); this.queue.push(key); } }; /** * 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) */隐藏开源应用程序中使用的API密钥 - java
我目前正在开发基于第三方网络API的桌面应用程序,并且已经为其程序注册并获得了两个访问密钥作为回报。但是,如果将这些键作为字符串粘贴到源代码中,那么任何人都可以拉回存储库的内容并轻松地找到它们。到目前为止,关于如何防止这种情况的最好的想法是将它们分别编译成一个类文件,对其进行模糊处理,然后再使用它,以便至少在源代码中不使用纯文本格式。但是,我是否缺少更好,更…
LeetCode题解堆排序和快速排序堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧
LeetCode题解斜着遍历遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索, 而搜索的核心就是遍历,而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能,而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候, 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历, 更少有情况是斜着遍历。那么这次就考考你, 怎么斜着遍历一个二…
LeetCode题解砝码的最小数量假设有三种重量的砝码,2g、3g、7g,对于任意重量物品,请设计一个函数getResult(weight),接收一个参数weight,返回所需砝码的最小数量。输入示例:const weight = 100;输出示例:getResult(weight) // 15 其中7g的14个,2g的1个题解:```phpfunction getResult($weigh…
LeetCode题解93. 复原IP地址给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。 示例:输入: \"25525511135\"输出: [\"255.255.11.135\", \"255.255.111.35\"]来源:力扣(LeetCode)链接:https://le…