首页 > 代码库 > 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.
这一题主要是要考虑到数据结构，首先我们定义一个双向链表来保存各个节点，并维护一个连表头和链表尾。同时我们用HashMap来保存节点的索引信息，存储key与其相对应的结点的索引。
每当执行get和set方法时，我们都将该结点放于链表头。
将结点移动到表头需要考虑两种情况。
1.该结点已经存在于链表中，此时我们需要先删除该链表中的该结点，然后将该结点添加到表头。
2.该节点是新增结点，在链表中并没有，则直接添加到连表头。
在执行set(key,value)方法时也需要考虑到两种情况。
1.在未超过容量的情况下，直接new一个该结点，并把该结点放置于表头。
2.超过容量的情况下，则首先需要删除链表尾，再将新的结点放于表头。
1 package LRU.Cache; 2 3 import java.util.HashMap; 4 import java.util.Map; 5 6 public class LRUCache { 7 Map <Integer,Node>map; 8 Node head; 9 Node tail;10 int len;11 int num;12 class Node{13 int key;14 int value;15 Node next;16 Node pre;17 public Node(int key,int value){18 this.key=key;19 this.value=http://www.mamicode.com/value;20 this.next=null;21 this.pre=null;22 }23 }24 public LRUCache(int capacity) {25 map =new HashMap<Integer,Node>(capacity);26 head=new Node(-1,-1);27 tail=new Node(-1,-1);28 head.next=tail;29 tail.pre=head;30 len=capacity;31 num=0;32 }33 public void moveToHead(Node n){34 if(n!=null){35 if(map.containsKey(n.key)){36 Node headNext=head.next;37 Node npre=n.pre;38 Node nnext=n.next;39 //remove n40 npre.next=nnext;41 nnext.pre=npre;42 }43 //put n to head44 Node headNext1=head.next;45 n.next=headNext1;46 headNext1.pre=n;47 head.next=n;48 n.pre=head;49 }else return;50 }51 public int removeTail(){52 Node tailPre=tail.pre;53 Node prePre=tailPre.pre;54 prePre.next=tail;55 tail.pre=prePre;56 return tailPre.key;57 }58 public int get(int key) {59 if(map.containsKey(key)){60 Node obj=map.get(key);61 moveToHead(obj);62 return obj.value;63 }else{64 return -1;65 }66 }67 68 public void set(int key, int value) {69 if(map.containsKey(key)){70 Node obj=map.get(key);71 obj.value=http://www.mamicode.com/value;72 moveToHead(obj);73 }else{74 Node obj=new Node(key,value);75 if(num<len){76 moveToHead(obj);77 map.put(key, obj);78 num++;79 }else{80 int remove=removeTail();81 map.remove(remove);82 moveToHead(obj);83 map.put(key, obj);84 }85 }86 }87 }
Leetcode LRU Cache