首页 > 代码库 > Problem LRU Cache
Problem LRU Cache
Problem Description:
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(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.
Solution:
1 public static class DoubleLinkedListNode { 2 int val; 3 int key; 4 DoubleLinkedListNode pre; 5 DoubleLinkedListNode next; 6 DoubleLinkedListNode(int key, int val) {this.key = key; this.val = val;pre = null; next = null;} 7 } 8 private int capacity; 9 10 private int len;11 private HashMap<Integer, DoubleLinkedListNode> map = 12 new HashMap<Integer, DoubleLinkedListNode>();13 private DoubleLinkedListNode head;14 private DoubleLinkedListNode end;15 public LRUCache(int capacity) {16 this.capacity = capacity;17 18 len = 0;19 }20 21 public int get(int key) {22 23 if (map.containsKey(key)) {24 DoubleLinkedListNode latest = map.get(key);25 removeNode(latest);26 setHead(latest);27 return latest.val;28 } else {29 return -1;30 }31 32 }33 public void removeNode(DoubleLinkedListNode node) {34 DoubleLinkedListNode cur = node;35 DoubleLinkedListNode pre = cur.pre;36 DoubleLinkedListNode post = cur.next;37 38 if (pre != null) {39 pre.next = post;40 } else {41 head = post;42 }43 44 if (post != null) {45 post.pre = pre;46 } else {47 end = pre;48 }49 }50 public void setHead(DoubleLinkedListNode node) {51 node.next = head;52 node.pre = null;53 if (head != null) {54 head.pre = node;55 }56 57 head = node;58 if (end == null) {59 end = node;60 }61 }62 public void set(int key, int value) {63 64 if (map.containsKey(key)) {65 DoubleLinkedListNode oldNode = map.get(key);66 oldNode.val = value;67 removeNode(oldNode);68 setHead(oldNode);69 } else {70 DoubleLinkedListNode newNode = new DoubleLinkedListNode(key, value);71 if (len < capacity) {72 setHead(newNode);73 map.put(key, newNode);74 len++;75 } else {76 map.remove(end.key);77 end = end.pre;78 if (end != null) {79 end.next = null;80 }81 82 setHead(newNode);83 map.put(key, newNode);84 }85 }86 87 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。