网站百度排名怎么做快,wordpress编辑文章很慢,协会网站建设方案书,wordpress 后台速度遇到困难#xff0c;不必慌张#xff0c;正是成长的时候#xff0c;耐心一点#xff01; 目录 前言一、题目介绍二、实现过程2.1 实现原理2.2 实现思路2.2.1 双向链表2.2.2 散列表 2.3 代码实现2.3.1 结构定义2.3.2 双向链表操作实现2.3.3 实现散列表的操作2.3.4 内存释放代… 遇到困难不必慌张正是成长的时候耐心一点 目录 前言一、题目介绍二、实现过程2.1 实现原理2.2 实现思路2.2.1 双向链表2.2.2 散列表 2.3 代码实现2.3.1 结构定义2.3.2 双向链表操作实现2.3.3 实现散列表的操作2.3.4 内存释放代码2.3.5 题目代码实现 总结 前言
本篇文章主要是为了记录实现LRU缓存的方法和思考的过程。
一、题目介绍 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类 LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。 如果插入操作导致关键字数量超过 capacity 则应该逐出最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例 输入 [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4 提示: 1 capacity 3000 0 key 10000 0 value 105 最多调用 2 * 105 次 get 和 put 下面是本人的一些废话不感兴趣可直接看实现过程
看完题目看到函数 get 和 put 必须以 O(1) 的平均时间复杂度运行第一反应是顺序存储的随机存取才可以实现O(1)的时间复杂度也就是说一定会有一块连续的存储空间存储数据且大小为capacity。可以把key对应连续的存储空间的下标但是看到提示里面的key的范围超出了capacity的范围那如何在让key在[0,capacity]循环呢脑子直接想到了循环队列的取余法因为最近用循环队列比较频繁。 但是经过取余后还是会造成出现重复的key该怎们解决呢突然想到数据结构里面的散列表的碰撞的处理立马去看关于散列表的介绍以前没学的东西现在又冒出来找我了。 看了以后觉得很神奇原来取余法是散列函数的一种并使用频繁的一种。然后又看了关于碰撞的处理书上介绍两种第一种叫开地址法第二种方法叫拉链法。 解决了碰撞问题那么如何实现最近最少使用一想到这是关于链表的题目慢慢想到了循环单链表头插法实现最近使用而尾结点一定是最少使用也就是当缓存空间达到capacity时需要删除的。但是写了一半代码发现当访问结点为尾结点时需要更改尾结点也就是需要尾结点的前驱。我知道在单链表中寻找某个结点前驱时间复杂度是O(n)不符合题意立马把代码删除。 经过思考心情里变得比较烦躁但又不想看题解因为想着现在正是考验我的时候想着这道题一定想要教会我什么。尝试让自己变得冷静不断地翻开数据结构这本书看到双向链表哎这不就是为了解决以O(1)时间复杂度访问某个结点前驱的问题嘛为什么没有马上想到是因为平时做的题目都是单链表双向链表用的太少了… 以上问题都解决了后刚开始使用开地址法的线性探查法解决碰撞时发现最后几个测试用例超时了但是说明思路是对的因为线性探访的最坏情况的时间复杂度就是O(n)。 然后改为使用了拉链法写代码用的时间不多调试用了很多时间最终在不放弃的情况下终于找到了代码的某处错误。真是太不容易了因为常规测试用例通过了在一些复杂的测试用例没通过又无法一步一步的调试只能不断地阅读代码最后发现是在某个很隐秘且常规测试用例很难覆盖的地方我当场麻了… 所幸最后还是一步一步的写出来了还是非常开心的感觉时间花的太值了
二、实现过程
2.1 实现原理
实现原理散列表双向链表 散列表解决了key重复问题并解决函数 get 和 put 必须以 O(1) 的平均时间复杂度运行的问题 双向链表解决了最近使用和最少使用的问题头插法解决最近使用尾结点解决了最少使用 结构图如图2.1所示
图2.1 LRU原理图 2.2 实现思路
2.2.1 双向链表
为了方便双向链表的插入和删除操作可以使用两个辅助结点一个伪头部和一个伪尾部实现了每个真实结点都有前驱和后继
图2.2.1 双向链表 2.2.2 散列表
这里主要想介绍解决碰撞问题的拉链法。 设散列表的大小为m,使用拉链法需要建立m条链表所有散列地址相同的元素放在同一条链表中如果某个地址中没有存放任何元素则对应的链表为空链表。设关键码key根据散列函数h计算出h(key)即可确定第h(key)条链表然后在该链表进行插入和删除及检索操作。 在本题中散列函数为取余法散列表的大小为capacity h ( k e y ) k e y % c a p a c i t y h(key) key \,\%\, capacity h(key)key%capacity 在本题中, h a s h K e y h ( k e y ) , h a s h V a l u e h a s h T a b l e [ h a s h K e y ] hashKey h(key), hashValue hashTable[hashKey] hashKeyh(key),hashValuehashTable[hashKey] 如下图所示
图2.2.1 散列表 2.3 代码实现
本篇文章的代码使用C语言实现
2.3.1 结构定义
//双向链表结点
struct DoubleNode
{int key; //真实的keyint value;struct DoubleNode* llink; //双向链表的前驱struct DoubleNode* rlink; //双向链表的后继
};//双向链表类型
//为了方便操作使用两个伪结点
struct DoubleList
{struct DoubleNode* dummyHead; //双向链表的伪头部struct DoubleNode* dummyRear; //双向链表的伪尾部
};//哈希结点的定义
//相同hashKey构成的链表的结点类型
struct HashNode
{struct DoubleNode* address; //指向双向链表的某个结点struct HashNode* next;
};//使用双向链表
//保存双向链表的头结点
//散列函数 取余法
//解决地址碰撞 拉链法
typedef struct
{struct DoubleList* doubleList; //双向链表struct HashNode** hashTable; //哈希表int capacity; //缓存空间大小int curCapacty; //已用空间
} LRUCache;
2.3.2 双向链表操作实现
//双向链表的操作
//初始化双向链表
void initDoubleList(struct DoubleList* doubleList)
{doubleList-dummyHead (struct DoubleNode*)calloc(1, sizeof(struct DoubleNode)); //初始化双向链表的伪头部doubleList-dummyRear (struct DoubleNode*)calloc(1, sizeof(struct DoubleNode)); //初始化双向链表的伪尾部//头和尾互连doubleList-dummyHead-rlink doubleList-dummyRear; doubleList-dummyRear-llink doubleList-dummyHead;
}//将某个结点向双向链表中的第一个结点前执行插入操作
void insertNodeToDoubleListFirst(struct DoubleList* doubleList, struct DoubleNode* node)
{node-rlink doubleList-dummyHead-rlink;node-llink doubleList-dummyHead;doubleList-dummyHead-rlink-llink node;doubleList-dummyHead-rlink node;
}//将node结点移动到双向链表的第一个结点
void moveNodeToHead(struct DoubleList* doubleList, struct DoubleNode* node)
{ //从双向链表中断开node-llink-rlink node-rlink;node-rlink-llink node-llink;//将断开的结点重新插入到双向链表的伪头部后insertNodeToDoubleListFirst(doubleList, node);
}2.3.3 实现散列表的操作
//哈希表的操作
//散列函数
//取余法
int hashFunc(int key, int m)
{return key % m;
}//在hashTable查看对应的hashKey的结点是否指向已存在的key
struct HashNode* getHashNode(struct HashNode** hashTable, int hashKey, int key)
{for (struct HashNode* hashValue hashTable[hashKey]; hashValue ! NULL; hashValue hashValue-next){if (hashValue-address-key key){return hashValue;}}return NULL;
}//往哈希表插入一个HashNode(头插法)
void insertHashNodeToHashTable(struct HashNode** hashTable, int hashKey,struct HashNode* hnode)
{ hnode-next hashTable[hashKey];hashTable[hashKey] hnode;
}//从哈希表hashTable[hashKey]-address dnode的结点断开在之前的链表
struct HashNode* deleteHashNodeFromHashTable(struct HashNode** hashTable, int hashKey, struct DoubleNode* dnode)
{struct HashNode* pre_hashNode hashTable[hashKey];struct HashNode* freeNode NULL;if (pre_hashNode-address dnode) //如果第一个为删除结点则将hashTable[hashKey] pre_hashNode-next{freeNode pre_hashNode;hashTable[hashKey] pre_hashNode-next;}else //否则需要寻找address为dnode的前驱结点{while (pre_hashNode-next-address ! dnode){pre_hashNode pre_hashNode-next;}freeNode pre_hashNode-next;pre_hashNode-next pre_hashNode-next-next;}return freeNode;
}
2.3.4 内存释放代码
//释放hashTable的内存
void hashTableNodeListFree(struct HashNode** hashTable, int capacity)
{ for(int hashKey 0; hashKey capacity; hashKey){//释放相同hashKey的链表结点内存for(struct HashNode* head hashTable[hashKey]; head ! NULL; NULL){struct HashNode* freeNode head;head head-next;free(freeNode);}}free(hashTable);
}//释放双向链表的内存
void doubleNodeListFree(struct DoubleList* doubleList)
{ //释放双向链表每一个数据结点空间for(struct DoubleNode* head doubleList-dummyHead; head ! NULL; NULL){struct DoubleNode* freeNode head;head head-rlink;free(freeNode);}//释放双向链表的头结点空间free(doubleList);
}2.3.5 题目代码实现
LRUCache* lRUCacheCreate(int capacity)
{LRUCache* obj (LRUCache*)calloc(1, sizeof(LRUCache));obj-capacity capacity;obj-hashTable (struct HashNode**)calloc(capacity, sizeof(struct HashNode*));obj-doubleList (struct DoubleList*)calloc(1, sizeof(struct DoubleList)); //初始化双向链表initDoubleList(obj-doubleList);return obj;
}int lRUCacheGet(LRUCache* obj, int key)
{int hashKey hashFunc(key, obj-capacity);struct HashNode* hashValue getHashNode(obj-hashTable, hashKey, key);if(hashValue ! NULL){moveNodeToHead(obj-doubleList, hashValue-address);return hashValue-address-value;}return -1;
}void lRUCachePut(LRUCache* obj, int key, int value)
{int hashKey hashFunc(key, obj-capacity);//查看当前的hashKey是否存在//存在则修改valuestruct HashNode* hashValue getHashNode(obj-hashTable, hashKey, key);if(hashValue ! NULL){hashValue-address-value value;moveNodeToHead(obj-doubleList, hashValue-address);return;}//当前的key对应的hashKey不存在//则将当前的key插入到hashTable中if (obj-curCapacty obj-capacity) //缓存空间未满 { //新建一个双向链表的结点struct DoubleNode* dnode (struct DoubleNode*)calloc(1, sizeof(struct DoubleNode));dnode-key key;dnode-value value;//新建一个HashNodestruct HashNode* hnode (struct HashNode*)calloc(1, sizeof(struct HashNode));hnode-address dnode; //插入到哈希表insertHashNodeToHashTable(obj-hashTable, hashKey, hnode);//将dnode插入到双链表的头insertNodeToDoubleListFirst(obj-doubleList, dnode);obj-curCapacty;}else //缓存空间已满 重用旧的结点-需要切断旧结点以前的联系-重新赋值-新生{//逐出最近未使用的关键字即双向链表的尾结点struct DoubleNode* dnode obj-doubleList-dummyRear-llink;//重置dnode在hashTable的位置struct HashNode* hnode deleteHashNodeFromHashTable(obj-hashTable, hashFunc(dnode-key,obj-capacity), dnode);//将dnode重新赋值dnode-key key;dnode-value value;//使用原来的哈希结点则 hnode-address dnode 可省略insertHashNodeToHashTable(obj-hashTable, hashKey,hnode);moveNodeToHead(obj-doubleList, dnode);}
}void lRUCacheFree(LRUCache* obj)
{//先释放双向链表的内存doubleNodeListFree(obj-doubleList);//释放哈希表的内存hashTableNodeListFree(obj-hashTable, obj-capacity);//释放缓存的头结点内存free(obj);
}总结
看到题目通过那瞬间真的非常开心但我知道代码还有很多大优化的空间希望能够持续不断地学习 仅仅用这篇文章记录本人解题的过程希望对读者有所帮助吧
