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;
}
}
}
這道題目還是挺有意思的。一開(kāi)始寫(xiě)出來(lái)超出時(shí)間了市咆，沒(méi)有怎么仔細(xì)分析秤掌。
兩個(gè)操作愁铺，
get,
set,最理想情況下都必須 O(1)
因?yàn)楫?dāng)超過(guò)限度后，需要把最不常用的刪除掉闻鉴，所以茵乱，為了使時(shí)間復(fù)雜度最低，必須得用鏈表孟岛。
然后瓶竭，get操作督勺，根據(jù)key返回value，復(fù)雜度要O(1)斤贰，所以要用HashMap
那么key value 各自是什么呢智哀？
key -> Integer, value -> Node(int key, int value)
然后我們get操作時(shí)，通過(guò)HashMap的key來(lái)找到Node再返回他的value荧恍。
然后再根據(jù)這個(gè)Node瓷叫，將其從當(dāng)前位置刪除，移動(dòng)到首結(jié)點(diǎn)位置送巡。
我們?cè)谶M(jìn)行set操作時(shí)摹菠，如果HashMap已經(jīng)存在了這個(gè)key，那么直接修改原值骗爆，然后移動(dòng)到鏈表頭部次氨。
如果沒(méi)有，則新建結(jié)點(diǎn)摘投，插到頭部煮寡。如果超過(guò)了限度，那么就把尾巴刪除掉谷朝。記得先從哈希表中刪除該鍵值對(duì)洲押，再刪除該結(jié)點(diǎn)（尾結(jié)點(diǎn)）武花。所以圆凰，Node里面必須要有key這個(gè)成員。然后再通過(guò)key去哈希表里面刪除對(duì)應(yīng)的鍵值對(duì)体箕。
這道題目就是得思考专钉，get, set操作需要那幾個(gè)原子級(jí)別的操作。
然后發(fā)現(xiàn)需要HashMap, 和鏈表累铅。然后需要有添加頭結(jié)點(diǎn)跃须，刪除特定結(jié)點(diǎn)的操作。
參考網(wǎng)頁(yè)：
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;
}
}
}
這道題目寫(xiě)了挺久娃兽，挺慚愧的菇民。昨天還和人說(shuō)這是簡(jiǎn)單題。投储。第练。
主要就是，我想到了用雙向鏈表玛荞，但覺(jué)得沒(méi)必要那么認(rèn)真娇掏。
后來(lái)越改錯(cuò)誤越多。
于是勋眯，看了下答案婴梧。再重寫(xiě)了下下梢。
剛剛學(xué)長(zhǎng)和我說(shuō)，Google今年三月份面過(guò)了塞蹭，被凍了一年孽江，不能再面了。番电。竟坛。
這是再開(kāi)玩笑嘛？钧舌？
Google, 就要這樣錯(cuò)過(guò)嗎担汤？
是不是很滑稽啊洼冻？崭歧？？
Anyway, Good luck, Richardo! -- 09/15/2016
