好吧，今天晚上赶项目确实是做不了三道题目了，最近项目在网络编程方面有些进步，学到了东西，有时间再积累下来，很深的体会就是，和别人一起写代码，虽然蛋疼但是比自己一个人写要好点，不过发现自己对链表和排序什么的都不太熟练啊，得好好认真练习，加油！
6
LRU Cache
public class LRUCache {
private int capacity;
private HashMap<Integer, Node> map;
private Node firstNode;
private Node lastNode;
public LRUCache(int capacity) {
this.capacity = capacity;
firstNode = new Node();
lastNode = new Node();
firstNode.next = lastNode;
lastNode.pre = firstNode;
map = new HashMap<Integer, Node>();
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
moveToHead(node);
return node.value;
} else {
return -1;
}
}
public void set(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
moveToHead(node);
}else{
if(map.size()>=capacity){
if(lastNode!=null&&capacity>0){
Node dNode = lastNode.pre;
lastNode.pre = dNode.pre;
dNode.pre.next = lastNode;
map.remove(dNode.key);
Node node = new Node();
node.key = key;
node.value = value;
moveToHead(node);
map.put(key, node);
}
}else{
Node node = new Node();
node.key = key;
node.value = value;
moveToHead(node);
map.put(key, node);
}
}
}
class Node {
Node pre;
Node next;
int key;
int value;
}
public void moveToHead(Node node) {
if (node.next != null&&node.pre != null) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
if (firstNode != null) {
node.pre = firstNode;
node.next = firstNode.next;
firstNode.next.pre = node;
firstNode.next = node;
}
}
}