区块链技术博客
www.b2bchain.cn

146. LRU缓存机制 — 双链表加Hash求职学习资料

本文介绍了146. LRU缓存机制 — 双链表加Hash求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

这道题我在面试时真实遇到过,当时使用的是字典,加数组;没考虑到链表,遗憾离场。

我们看原题:

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。  获取数据 get(key) - 如果关键字 (key) 存在于缓存中,则获取关键字的值(总是正数),否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字/值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );  cache.put(1, 1); cache.put(2, 2); cache.get(1);       // 返回  1 cache.put(3, 3);    // 该操作会使得关键字 2 作废 cache.get(2);       // 返回 -1 (未找到) cache.put(4, 4);    // 该操作会使得关键字 1 作废 cache.get(1);       // 返回 -1 (未找到) cache.get(3);       // 返回  3 cache.get(4);       // 返回  4

链接:https://leetcode-cn.com/problems/lru-cache

分析:

双链表的特点:

  • 删除、更新、插入的时间复杂度为O(1)
  • 缺点:查找为O(n)

我们针对查找为O(n)的缺点,通过hash表存起来,用空间换时间。
key:值
value:node节点
此外在处理链表时通常会会引入fakeNode,本题中分别增加了fakeHead、fakeTail

注意:

  • LRU缓存是有最大容量的、超过了要删除不常用的,即最后一个
  • 注意新增时,有可能是更新,这时需要把之前的移到头结点、否则头部新增一个节点

c++:代码
“`
struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
unordered_map cache;
DLinkedNode* head;
DLinkedNode* tail;
int size;
int capacity;

public:
LRUCache(int _capacity): capacity(_capacity), size(0) {
// 使用伪头部和伪尾部节点
head = new DLinkedNode();

这道题我在面试时真实遇到过,当时使用的是字典,加数组;没考虑到链表,遗憾离场。

我们看原题:

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。  获取数据 get(key) - 如果关键字 (key) 存在于缓存中,则获取关键字的值(总是正数),否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字/值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );  cache.put(1, 1); cache.put(2, 2); cache.get(1);       // 返回  1 cache.put(3, 3);    // 该操作会使得关键字 2 作废 cache.get(2);       // 返回 -1 (未找到) cache.put(4, 4);    // 该操作会使得关键字 1 作废 cache.get(1);       // 返回 -1 (未找到) cache.get(3);       // 返回  3 cache.get(4);       // 返回  4

链接:https://leetcode-cn.com/problems/lru-cache

分析:

双链表的特点:

  • 删除、更新、插入的时间复杂度为O(1)
  • 缺点:查找为O(n)

我们针对查找为O(n)的缺点,通过hash表存起来,用空间换时间。
key:值
value:node节点
此外在处理链表时通常会会引入fakeNode,本题中分别增加了fakeHead、fakeTail

注意:

  • LRU缓存是有最大容量的、超过了要删除不常用的,即最后一个
  • 注意新增时,有可能是更新,这时需要把之前的移到头结点、否则头部新增一个节点

c++:代码
“`
struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
unordered_map cache;
DLinkedNode* head;
DLinkedNode* tail;
int size;
int capacity;

public:
LRUCache(int _capacity): capacity(_capacity), size(0) {
// 使用伪头部和伪尾部节点
head = new DLinkedNode();

这道题我在面试时真实遇到过,当时使用的是字典,加数组;没考虑到链表,遗憾离场。

我们看原题:

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。  获取数据 get(key) - 如果关键字 (key) 存在于缓存中,则获取关键字的值(总是正数),否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字/值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );  cache.put(1, 1); cache.put(2, 2); cache.get(1);       // 返回  1 cache.put(3, 3);    // 该操作会使得关键字 2 作废 cache.get(2);       // 返回 -1 (未找到) cache.put(4, 4);    // 该操作会使得关键字 1 作废 cache.get(1);       // 返回 -1 (未找到) cache.get(3);       // 返回  3 cache.get(4);       // 返回  4

链接:https://leetcode-cn.com/problems/lru-cache

分析:

双链表的特点:

  • 删除、更新、插入的时间复杂度为O(1)
  • 缺点:查找为O(n)

我们针对查找为O(n)的缺点,通过hash表存起来,用空间换时间。
key:值
value:node节点
此外在处理链表时通常会会引入fakeNode,本题中分别增加了fakeHead、fakeTail

注意:

  • LRU缓存是有最大容量的、超过了要删除不常用的,即最后一个
  • 注意新增时,有可能是更新,这时需要把之前的移到头结点、否则头部新增一个节点

c++:代码
“`
struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
unordered_map cache;
DLinkedNode* head;
DLinkedNode* tail;
int size;
int capacity;

public:
LRUCache(int _capacity): capacity(_capacity), size(0) {
// 使用伪头部和伪尾部节点
head = new DLinkedNode();

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 146. LRU缓存机制 — 双链表加Hash求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们