hard
https://leetcode.com/problems/lru-cache/
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get
and put
.get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.put(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4
思路: use a hashmap + doubly linked List: (head)..(pre)<—>(cur)<—>(next)..(end)
Always set the head for the most recent accessed node.
watch edge case like 1 node in list. Deleting head/tail, we need to set head/tail simultaneously.
Complexity: Time O(1) Space O(N)
public class LRUCache { class Node{ Node pre; Node next; int val; int key;//need key fields for look back to delete in Map public Node(int key,int value){ this.val = value; this.key = key; } } private void removeNode(Node n){ Node preN = n.pre; Node nextN = n.next; if(n == head)head = nextN;//watch case of deleting head & end if(n == end)end = preN;// if(preN != null)preN.next = nextN; if(nextN != null)nextN.pre = preN; } public void setHead(Node n){//head is most recent val n.next = head; n.pre = null; if(head != null) head.pre = n; head = n; if(end == null)end = head;//actually when only head in list } //instance variable Node head = null; Node end = null; HashMap<Integer,Node> map = new HashMap<>(); //<val, node in list> int capacity; public LRUCache(int capacity) { this.capacity = capacity; } public int get(int key) { if(!map.containsKey(key))return -1; Node cur = map.get(key); removeNode(cur); setHead(cur); return cur.val; } public void put(int key, int value) { if(!map.containsKey(key)){ if(map.size() >= capacity){ map.remove(end.key); removeNode(end); } Node cur = new Node(key, value); map.put(key, cur); setHead(cur); }else{//update value Node cur = map.get(key); cur.val = value; removeNode(cur); setHead(cur); } } } /** * 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); */
No comments:
Post a Comment