LeetCode——LRU 缓存机制(借助Map)-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

LeetCode——LRU 缓存机制(借助Map)

简介: 解决这个问题之前,我们首先要读懂题意,知道什么是LRU缓存机制,LRU缓存机制指的是优先删除那些最久未使用的缓存,在本题中,一个缓存被put或者get都算是一次使用,明白这一点,也就理解了本题的核心题意。

题目描述

image.png
image.png

解题思路

解决这个问题之前,我们首先要读懂题意,知道什么是LRU缓存机制,LRU缓存机制指的是优先删除那些最久未使用的缓存,在本题中,一个缓存被put或者get都算是一次使用,明白这一点,也就理解了本题的核心题意。

1: 初始化构造函数

var LRUCache = function (capacity) {
    this.capacity = capacity;
    this.map = new Map();
};

2:实现get方法

  • 判断map中是都有目标key。

    • 没有则返回-1
    • 有,则保存对应的值,然后删除键值对,重新存,然后返回对应的值。这里之所以要进行重新存储,是为了更新首个元素为最久未使用的元素。
LRUCache.prototype.get = function (key) {
    // 如果map中有这个key存在则返回,反之返回-1
    if (this.map.has(key)) {
        const value = this.map.get(key);
        this.map.delete(key);
        this.map.set(key,value)
        return this.map.get(key);
    } else {
        return -1;
    }
};

3:实现put方法

  • 首先判断要存储的key是否存在

    • 存在:删除进行重新存储
    • 不存在:首先判断map的尺寸是否大于构造函数中的容量,如果大于则删除map的首元素,删除方法是map.entries().next().value[0],如果不大于则直接存储。
LRUCache.prototype.put = function (key, value) {
    // 首先判断这个key存在吗,存在则删除,重新放置 反之直接放置
    if (this.map.has(key)) {
        this.map.delete(key);
        this.map.set(key,value);
    } else {
        // 判断map的大小是否比题目给定的容量大
        if (this.map.size >= this.capacity) {
            this.map.delete(this.map.entries().next().value[0]);
            this.map.set(key,value)
        } else {
            this.map.set(key,value)
        }
    }
};

题目反思

  • 通过本题应该学会使用map的各种API,从这题可以看出,我对map的各种API还不够熟系。
  • map.entries()变为了一个可迭代的对象。
  • next()会将一个可迭代对象变为一个普通对象。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: