赞
踩
Problem: 146. LRU 缓存
主要说明大致思路,具体实现看代码。
1.为了实现题目中的O(1)时间复杂度的get与put方法,我们利用哈希表和双链表的结合,将key作为键,对应的链表的节点作为值(也就是在此处我们用一个节点类作为值);
2.定义双链表的节点类,其中包含每次put的键与对应的值,还包括前驱、后驱指针;
3.编写双链表的实现类,并实现:3.1.初始化一个双链表(创建虚拟头、尾节点;由于我们要实现将最就不使用的节点删除,我们在此使用尾插法即每次链表尾部位最近使用的,表头为最久不适用的);
3.2.实现尾插一个节点;
3.3.实现删除一个给定的节点;
3.4.实现从表头删除一个节点(删除最久不使用的节点)
3.5.返回链表的长度
4.实现LRUCache类:
4.1. 创建哈希表map与双链表cache;
4.2. 为了不直接在get与put中对map与cache操作带来麻烦(主要操作是同步在mao中添加key同时在cache中增、删、改对应节点的值),我们封装实现一些API(具体操作实现看代码)
4.3. 实现get与put方法(直接看代码)
时间复杂度:
O ( n ) O(n) O(n);其中 n n n为要操作的次数
空间复杂度:
O ( n ) O(n) O(n)
/** * Node class */ class Node { public int key; public int val; public Node next; public Node prev; public Node(int k, int v) { this.key = k; this.val = v; } } class DoubleList { //The dummy node of head and tail to a double linked list private Node head; private Node tail; //The size of a linked list private int size; public DoubleList() { //Initialize the element of double linked list head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; size = 0; } // Add node x at the end of the list, time O(1) // Tail insertion method of bidirectional linked list // with virtual head and tail nodes public void addLast(Node x) { x.prev = tail.prev; x.next = tail; tail.prev.next = x; tail.prev = x; size++; } // Delete the x node in the linked list (x must exist) // Since it is a double-linked list and given to the target Node, // time O(1) public void remove(Node x) { x.prev.next = x.next; x.next.prev = x.prev; size--; } // Delete the first node in the linked list // and return the node, time O(1) public Node removeFirst() { if (head.next == null) { return null; } Node first = head.next; remove(first); return first; } // Return list length, time O(1) public int size() { return size; } } class LRUCache { private HashMap<Integer, Node> map; private DoubleList cache; //Max capacity private int cap; public LRUCache(int capacity) { this.cap = capacity; map = new HashMap<>(); cache = new DoubleList(); } // Upgrade a key to the most recently used private void makeRecently(int key) { Node x = map.get(key); // Delete this node from the linked list first cache.remove(x); // Move back to the end of the line cache.addLast(x); } // Add the most recently used element private void addRecently(int key, int val) { Node x = new Node(key, val); // The end of the list is the most recently used element cache.addLast(x); // Add the mapping of the key to the map map.put(key, x); } // Delete a key private void deleteKey(int key) { Node x = map.get(key); // Delete from the linked list cache.remove(x); // Delete from map map.remove(key); } // Delete the element that has been unused the longest private void removeLeastRecently() { // The first element at the head of the list is the one // that has been unused for the longest time Node deletedNode = cache.removeFirst(); // Delete its key from the map int deleteKey = deletedNode.key; map.remove(deleteKey); } public int get(int key) { if (!map.containsKey(key)) { return -1; } // Upgrade the data to the most recently used makeRecently(key); return map.get(key).val; } public void put(int key, int value) { if (map.containsKey(key)) { // Delete old data deleteKey(key); // The newly inserted data is the latest data addRecently(key, value); return; } if (cap == cache.size()) { // Delete the element that has been unused the longest removeLeastRecently(); } // Add as recently used element addRecently(key, value); } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。