Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

146. LRU 缓存 #52

Open
webVueBlog opened this issue Sep 5, 2022 · 0 comments
Open

146. LRU 缓存 #52

webVueBlog opened this issue Sep 5, 2022 · 0 comments

Comments

@webVueBlog
Copy link
Owner

146. LRU 缓存

Description

Difficulty: 中等

Related Topics: 设计, 哈希表, 链表, 双向链表

请你设计并实现一个满足  约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 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 <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105getput

Solution

Language: JavaScript

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
 this.map = new Map()
 this.capacity = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
 if (this.map.has(key)) {
  let value = this.map.get(key)
  // 重新set,相当于更新到 map 最后
  this.map.delete(key)
  this.map.set(key, value)
  return value
 }
 return -1
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
 if (this.map.has(key)) {
  this.map.delete(key)
 }

 this.map.set(key, value)

 if (this.map.size > this.capacity) {
  this.map.delete(this.map.keys().next().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)
 */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant