lrucacheleetcode-Leetcode:项目是用javascript和c++解决问题

LRU (Least Recently Used) 缓存是一种常用的内存管理策略，广泛应用于计算机科学，尤其是在数据库、操作系统和编程语言中。LRU策略的基本思想是：当缓存满时，最近最少使用的数据将被移除，以腾出空间给新数据。在LeetCode上，LRU缓存是一个常见的算法问题，它要求设计一个数据结构来模拟LRU的行为。 在JavaScript和C++中实现LRU缓存，主要涉及到数据结构和算法的设计。下面我们将深入探讨这两个语言如何实现LRU缓存，并通过LeetCode的相关题目来阐述其实现细节。 ### JavaScript实现LRU缓存 在JavaScript中，我们可以使用内置的数据结构，如`Map`和`Set`来实现LRU缓存。`Map`用于存储键值对，而`Set`用于保存最近使用的键。当添加新的元素时，如果缓存已满，我们就从`Map`中移除最不常使用的键值对，同时从`Set`中删除对应的键。 ```javascript class LRUCache { constructor(capacity) { this.capacity = capacity; this.cache = new Map(); this.recent = new Set(); } get(key) { if (this.cache.has(key)) { this.recent.delete(key); this.recent.add(key); return this.cache.get(key); } return -1; } put(key, value) { if (this.cache.has(key)) { this.recent.delete(key); } else if (this.cache.size === this.capacity) { let leastRecentKey = this.recent.values().next().value; this.cache.delete(leastRecentKey); this.recent.delete(leastRecentKey); } this.recent.add(key); this.cache.set(key, value); } } ``` ### C++实现LRU缓存 在C++中，我们可以使用`std::unordered_map`和`std::list`来实现LRU缓存。`unordered_map`用于快速查找键值对，`list`用于维护键的顺序。当我们添加新元素时，将新元素插入到`list`的头部，并更新`unordered_map`。 ```cpp #include <iostream> #include <unordered_map> #include <list> using namespace std; class LRUCache { public: LRUCache(int capacity) : cap(capacity) {} int get(int key) { if (cache.find(key) != cache.end()) { lru.splice(lru.begin(), lru, cache[key]); return cache[key]->second; } return -1; } void put(int key, int value) { if (cache.find(key) != cache.end()) { lru.erase(cache[key]); } else { if (cache.size() == cap) { cache.erase(lru.rbegin()->first); lru.pop_back(); } } lru.push_front(make_pair(key, value)); cache[key] = lru.begin(); } private: int cap; list<pair<int, int>> lru; unordered_map<int, list<pair<int, int>>::iterator> cache; }; ``` 在LeetCode上，有一个名为"LRU缓存"（LRU Cache）的问题（编号146），正是要求实现这样一个数据结构。这个题目是理解LRU缓存机制和实现的好入口，可以帮助开发者巩固数据结构和算法基础。 通过上述两种语言的实现，我们可以看到，尽管实现细节有所不同，但核心思路是一致的：维护一个固定大小的缓存，并根据最近使用频率决定何时以及如何替换旧数据。理解并熟练掌握这种策略对于解决其他涉及内存管理和性能优化的问题至关重要。