首页 > 代码库 > Leetcode-LRU Cache
Leetcode-LRU Cache
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.
Analysis:
Use double linked list.
Solution:
1 class Node{ 2 int key; 3 int val; 4 Node pre; 5 Node next; 6 public Node(int k, int v){ 7 key= k; 8 val = v; 9 pre = null;10 next = null;11 }12 }13 14 public class LRUCache {15 16 17 Map<Integer,Node> record;18 Node preHead,end;19 int maxCapa;20 int curCapa;21 22 public LRUCache(int capacity) {23 record = new HashMap<Integer,Node>();24 preHead = new Node(-1,-1);25 end = null;26 maxCapa = capacity;27 curCapa = 0;28 }29 30 public int get(int key) {31 if (!record.containsKey(key)) return -1;32 Node cur = record.get(key);33 if (cur==end) return cur.val;34 35 cur.pre.next = cur.next;36 cur.next.pre = cur.pre;37 end.next = cur;38 cur.next = null;39 cur.pre = end;40 end = cur; 41 return cur.val;42 }43 44 public void set(int key, int value) {45 if (maxCapa==0) return;46 47 if (record.containsKey(key)){48 Node cur = record.get(key);49 cur.val = value;50 this.get(key);51 } else {52 if (curCapa==maxCapa){53 Node cur = preHead.next;54 preHead.next = cur.next;55 record.remove(cur.key);56 curCapa--; 57 }58 59 curCapa++;60 Node cur = new Node(key,value);61 record.put(key,cur);62 if (curCapa==1){63 preHead.next = cur;64 cur.pre = preHead;65 end = cur;66 } else {67 end.next = cur;68 cur.pre = end;69 end = cur;70 } 71 }72 }73 }
Leetcode-LRU Cache
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。