leetcode LRUCache

50 阅读 0 评论 33 点赞

我是靠谱客的博主飘逸百合，最近开发中收集的这篇文章主要介绍leetcode LRUCache，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

转载请注明来自souldak，微博:@evagle

接口就两个，get和set。

但是第一次写TLE，开始用的是单链表，单链表有个不好的地方是，容量满了之后，要删除最后一个元素会及其困难，必须从表头开始遍历。

为了不遍历，必须使用双向链表，然后记录链表结尾。

然后还有一个可以改进的地方是：get的时候，为了不从头开始扫描，用HashMap记录所有元素的引用。直接从Hashmap中取，O（1），然后再更新这个节点到链表头部，也是O（1）.set 的时候，先从Hashmap中判断是否已经存在，存在的话修改值，然后移动到头部，如果不存在，新建节点，插入链表头部。也是O(1). 这样的话就不会超时了。

注意点: 如果移动的是最后一个元素的时候，要注意不要引用这个元素的next，它是空指针。