146LRU 缓存机制

题目链接

难度：中等

思路分析：

编程题。

链表，数组，对象都可以。

想

一

想

再

看

答

案

想

一

想

再

看

答

案

代码：

链表：

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
	this.map = new Map() // map默认记住插入的顺序
	this.max = capacity // 最大数量
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
	const value = this.map.get(key) || -1
	if (value !== -1) {
		this.map.delete(key) // 删除更新插入顺序
		this.map.set(key, value)
	}
	return value
}
/**
 * @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.max < this.map.size) {
		const mapKeys = this.map.keys() // 获取遍历值
		const oldKey = mapKeys.next().value // map插入顺序 默认第一个即最早插入的值
		this.map.delete(oldKey) // 删除最早的值
	}
}

对象/map

// TODO: map: 用时88.91, 内存100
/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
	this.map = new Map() // map默认记住插入的顺序
	this.max = capacity // 最大数量
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
	const value = this.map.get(key) || -1
	if (value !== -1) {
		this.map.delete(key) // 删除更新插入顺序
		this.map.set(key, value)
	}
	return value
}
/**
 * @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.max < this.map.size) {
		const mapKeys = this.map.keys() // 获取遍历值
		const oldKey = mapKeys.next().value // map插入顺序 默认第一个即最早插入的值
		this.map.delete(oldKey) // 删除最早的值
	}
}

数组

//  数组: 用时36, 内存100;
/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
	this.keyArr = [] // key最近使用的值
	this.data = {} // 存储数据
	this.max = capacity // 最大数量
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
	const index = this.findIndex(key)
	if (index !== -1) {
		this.updateNew(key, index)
		return this.data[key]
	}
	return -1
}
// 更新key的新鲜值
LRUCache.prototype.updateNew = function(key, index) {
	this.keyArr.splice(index, 1)
	this.keyArr.unshift(key) // 更新key的新鲜值
}

// 寻找key的位置
LRUCache.prototype.findIndex = function(key) {
	return this.keyArr.findIndex(item => {
		return item === key
	})
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
	const index = this.findIndex(key)
	if (index !== -1) {
		this.updateNew(key, index)
		this.data[key] = value
	} else {
		this.data[key] = value
		this.keyArr.unshift(key)
	}
	if (this.max < this.keyArr.length) {
		this.keyArr.pop() // 删除最后一个值
	}
}

鼓励我一下：

觉得还不错的话，给我的项目点个star吧

点个Star支持我一下~