leetcode 146

思路

什么是LRU緩存？

LRU（Least Recently Used）緩存是一種常見的緩存淘汰策略，核心思想是：當緩存容量滿時，優先淘汰最久未使用的數據。LeetCode 146 題要求實現一個支持get和put操作的 LRU 緩存，且操作時間復雜度需為 O (1)

核心思路

在 JavaScript 中，Map對象天然具備鍵值對插入順序保留的特性，且map.keys().next().value可獲取最早插入的鍵（最久未使用）。利用這一點，可很好實現刪除最久未使用數據的功能

• 訪問順序維護：每次訪問鍵時，通過delete+set將其移到 Map 末尾（表示最近使用）
• 淘汰策略：容量滿時，刪除 Map 的第一個鍵（最早插入的鍵）

關鍵操作解析

1. get(key)操作
   • 若鍵存在，通過delete+set將其重新插入 Map，使其成為最新訪問的鍵
   • 原理：Map 會保留鍵的插入順序，重新插入相當于將鍵移到末尾
2. put(key, val)操作
   • 若鍵已存在，同樣通過delete+set更新值并刷新順序。
   • 若鍵不存在且容量滿，通過map.keys().next().value獲取最早插入的鍵（最久未使用）并刪除，再插入新鍵

時間復雜度：O(1) 空間復雜度: O(capacity)

實現

class LRUCache {constructor(capacity) {this.capacity = capacity;this.cacheMap = new Map();}get(key) {const isExit = this.cacheMap.has(key);if (isExit) {const val = this.cacheMap.get(key);this.cacheMap.delete(key);this.cacheMap.set(key, val);return val;}return -1;}put(key, val) {const isExit = this.cacheMap.has(key);if (isExit) {this.cacheMap.delete(key)this.cacheMap.set(key, val)} else {if (this.capacity <= this.cacheMap.size) {// 超出緩存容量，刪除最久未使用的keyconst first = this.cacheMap.keys().next().value;this.cacheMap.delete(first)}this.cacheMap.set(key, val)}}
}