My code:
public class LRUCache {
private class Node {
Node next;
Node prev;
int key;
int val;
private Node(int key, int val) {
this.key = key;
this.val = val;
}
}
private final int capacity;
private int counter;
private HashMap<Integer, Node> LRU;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
counter = 0;
LRU = new HashMap<Integer, Node>();
}
public int get(int key) {
if (LRU.containsKey(key)) {
Node temp = LRU.get(key);
int ret = temp.val;
remove(temp);
addToFirst(temp);
return ret;
}
else
return -1;
}
public void set(int key, int value) {
if (LRU.containsKey(key)) {
Node temp = LRU.get(key);
temp.val = value;
remove(temp);
addToFirst(temp);
}
else {
counter++;
Node temp = new Node(key, value);
addToFirst(temp);
LRU.put(key, temp);
if (counter > capacity) {
LRU.remove(tail.key);
remove(tail);
counter = capacity;
}
}
}
private void remove(Node temp) {
if (temp == null)
return;
if (temp.prev == null) { // head node
if (temp.next == null) {
head = null;
tail = null;
}
else {
head = temp.next;
temp.next.prev = null;
}
}
else if (temp.next == null) { // tail nod
if (temp.prev == null) {
head = null;
tail = null;
}
else {
tail = temp.prev;
temp.prev.next = null;
}
}
else {
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
}
}
private void addToFirst(Node p) {
if (p == null)
return;
if (head == null) {
head = p;
tail = p;
}
else {
head.prev = p;
p.next = head;
p.prev = null;
head = p;
}
}
}
这道题目还是挺有意思的。一开始写出来超出时间了，没有怎么仔细分析。
两个操作，
get,
set,最理想情况下都必须 O(1)
因为当超过限度后，需要把最不常用的删除掉，所以，为了使时间复杂度最低，必须得用链表。
然后，get操作，根据key返回value，复杂度要O(1)，所以要用HashMap
那么key value 各自是什么呢？
key -> Integer, value -> Node(int key, int value)
然后我们get操作时，通过HashMap的key来找到Node再返回他的value。
然后再根据这个Node，将其从当前位置删除，移动到首结点位置。
我们在进行set操作时，如果HashMap已经存在了这个key，那么直接修改原值，然后移动到链表头部。
如果没有，则新建结点，插到头部。如果超过了限度，那么就把尾巴删除掉。记得先从哈希表中删除该键值对，再删除该结点（尾结点）。所以，Node里面必须要有key这个成员。然后再通过key去哈希表里面删除对应的键值对。
这道题目就是得思考，get, set操作需要那几个原子级别的操作。
然后发现需要HashMap, 和链表。然后需要有添加头结点，删除特定结点的操作。
参考网页：
http://www.programcreek.com/2013/03/leetcode-lru-cache-java/
Anyway, Good luck, Richardo!
My code:
public class LRUCache {
private class ListNode {
ListNode pre;
ListNode next;
int key;
int val;
ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
HashMap<Integer, ListNode> map = new HashMap<Integer, ListNode>();
int capacity = 0;
ListNode dummy = new ListNode(-1, -1);
ListNode tail = dummy;
int size = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
ListNode node = map.get(key);
remove(node);
addFirst(node);
return node.val;
}
public void set(int key, int value) {
if (map.containsKey(key)) {
ListNode node = map.get(key);
node.val = value;
remove(node);
// insert it at the head of list
addFirst(node);
}
else {
ListNode node = new ListNode(key, value);
map.put(key, node);
addFirst(node);
size++;
if (size > capacity) {
map.remove(tail.key);
remove(tail);
size--;
}
}
}
private void addFirst(ListNode node) {
ListNode head = dummy.next;
dummy.next = node;
node.pre = dummy;
node.next = head;
if (head != null) {
head.pre = node;
}
else {
tail = node;
}
}
private void remove(ListNode node) {
if (node.next == null) {
tail = node.pre;
node.pre.next = node.next;
}
else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
}
}
这道题目写了挺久，挺惭愧的。昨天还和人说这是简单题。。。
主要就是，我想到了用双向链表，但觉得没必要那么认真。
后来越改错误越多。
于是，看了下答案。再重写了下。
刚刚学长和我说，Google今年三月份面过了，被冻了一年，不能再面了。。。
这是再开玩笑嘛？？
Google, 就要这样错过吗？
是不是很滑稽啊？？？
Anyway, Good luck, Richardo! -- 09/15/2016
