运用你所掌握的数据结构,设计和实现一个 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
这道题基本的思路就是:
- 因为要求是查找,删除都是O(1)的时间复杂度,那么 整体需要一个哈希表加上双向链表这种数据结构实现
- HashMap中的key就是文中要求的key,value是一个双向链表,里边存储的有key 与想要的value.也就是:
HashMap<key, DoubleLinkedNode>
其中DoubleLinkedNode的存储的就是key,value - 说下具体的业务逻辑:
(1)在get的时候,先判断是否有这个,没有就返回-1,在使用完这个key后要把这个值更新到链表的头部,因为LRU算法的意思就是给一个比较小的固定的空间存储,当你插入的数量大于里边的容量的时候,也就是满了,这时候就要看那个值很久没用了,然后把它删除,再把值插入到队列的头部。
(2)put ()时候,首先要看里边是否已经有这个key,有的话直接更新存储的值。没有的话,首先看下当前容量是否已经满了,如果已经满了,需要进行删除最后一个值,然后再插入新的值到首部,没有满那么直接插入到首部。
代码如下:
/** * leetcode -- 146. LRU缓存机制 * @author zhx */ public class LRUCache { private static class DLinkedNode{ int key; int value; DLinkedNode pre; DLinkedNode next; } /** * 在头节点插入一新节点 * @param node */ private void addNode(DLinkedNode node){ node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; } /** * 删除元素操作 * @param node */ private void removeNode(DLinkedNode node){ DLinkedNode pre = node.pre; DLinkedNode post = node.next; pre.next = post; post.pre = pre; } /** * 摘除一个元素并把它移动到开头 */ private void moveToHead(DLinkedNode node){ this.removeNode(node); this.addNode(node); } /** * 弹出最尾巴的节点 * @return */ private DLinkedNode popTail(){ DLinkedNode res = tail.pre; this.removeNode(res); return res; } private HashMap<Integer, DLinkedNode> cache = new HashMap<>(); private int count; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity){ this.capacity = capacity; this.count = 0; head = new DLinkedNode(); head.pre = null; tail = new DLinkedNode(); tail.next = null; head.next = tail; tail.pre = head; } public int get(int key){ DLinkedNode node = cache.get(key); if(node == null) { return -1; }else{ this.moveToHead(node); return node.value; } } public void put(int key, int value){ DLinkedNode node = cache.get(key); if(node == null){ DLinkedNode newNode = new DLinkedNode(); newNode.key = key; newNode.value = value; this.cache.put(key, newNode); this.addNode(newNode); ++count; if(count > capacity){ //最后一个节点弹出 DLinkedNode tail = this.popTail(); this.cache.remove(tail.key); count--; } }else{ //cache命中,更新cache node.value = value; this.moveToHead(node); } } }