LeetCode——LRU 緩存機制（借助Map）

題目描述

解題思路

解決這個問題之前，我們首先要讀懂題意，知道什麼是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()會将一個可疊代對象變為一個普通對象。