五刷 06/2022
Version #1 Doubly Linked List + HashMap
Runtime: 96 ms, faster than 30.82% of Java online submissions for LRU Cache.
Memory Usage: 125.7 MB, less than 47.57% of Java online submissions for LRU Cache.
class LRUCache {
class ListNode {
public ListNode prev, next;
public int key;
public int val;
public ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
private Map<Integer, ListNode> nodes;
private ListNode head, tail;
private int cap;
// We need a doubly-linked list to serve as the cache
// In order to make get/put O(1) we need hashmap to keep track of the nodes in the list
private void addFirst(ListNode node) {
// head -> head.next
// head -> node -> head.next
ListNode nextNode = head.next;
head.next = node;
node.prev = head;
node.next = nextNode;
nextNode.prev = node;
}
private ListNode removeLast() {
// tail.prev.prev -> tail.prev -> tail
// tail.prev.prev -> tail
ListNode prevNode = tail.prev;
if (prevNode == head) {
return null;
}
prevNode.prev.next = tail;
tail.prev = prevNode.prev;
return prevNode;
}
private void removeNode(ListNode node) {
ListNode prev = node.prev;
ListNode next = node.next;
prev.next = next;
next.prev = prev;
}
public LRUCache(int capacity) {
nodes = new HashMap<>();
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head.next = tail;
tail.prev = head;
cap = capacity;
}
public int get(int key) {
if (!nodes.containsKey(key)) {
return -1;
}
ListNode node = nodes.get(key);
if (node.prev != head) {
removeNode(node);
addFirst(node);
}
return node.val;
}
public void put(int key, int value) {
if (nodes.containsKey(key)) {
ListNode node = nodes.get(key);
node.val = value;
if (node.prev != null) {
removeNode(node);
addFirst(node);
}
return;
}
ListNode node = new ListNode(key, value);
nodes.put(key, node);
addFirst(node);
if (nodes.size() > cap) {
ListNode last = removeLast();
nodes.remove(last.key);
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
这次做的有点不一样，一开始没有考虑remove的时候需要把key从map里面移除
写到最后的时候不得不加了一个反向的keyMap把ListNode和key联系在一起
看了以前的写法，可以直接在ListNode里面加一个key的field
anyway这次只写了20分钟，还是挺快的
45.21 %
class LRUCache {
class ListNode {
ListNode prev, next;
int val;
public ListNode(int val) {
this.val = val;
}
}
// doubly linked list
private Map<Integer, ListNode> map;
private Map<ListNode, Integer> keyMap;
private ListNode head, tail;
private int capacity;
private int size;
public LRUCache(int capacity) {
map = new HashMap<>();
keyMap = new HashMap<>();
this.capacity = capacity;
this.size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
// check if key exist -> remove list node from original node, intsert at tail
if (!map.containsKey(key)) {
return -1;
}
ListNode curr = map.get(key);
if (curr.next != tail) {
removeNode(curr);
appendNode(curr);
}
return curr.val;
}
public void put(int key, int value) {
// check if key exist -> remove
// insert at tail
// check size -> check if we need to remove the 1st node or not
ListNode curr = null;
if (map.containsKey(key)) {
curr = map.get(key);
if (curr.next != tail) {
removeNode(curr);
appendNode(curr);
}
curr.val = value;
} else {
curr = new ListNode(value);
map.put(key, curr);
keyMap.put(curr, key);
appendNode(curr);
size++;
if (size > capacity) {
ListNode outdatedNode = head.next;
removeNode(head.next);
map.remove(keyMap.get(outdatedNode));
keyMap.remove(outdatedNode);
}
}
}
private void removeNode(ListNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void appendNode(ListNode node) {
ListNode prev = tail.prev;
prev.next = node;
node.prev = prev;
node.next = tail;
tail.prev = node;
}
}
[3RD TRY]
Think about thread safety...
I just added synchronized key word to get and put
Should try ReentrantLock in the future
60.20 %
import java.util.concurrent.ConcurrentHashMap;
public class LRUCache {
private LinkedHashMap linkedHashMap;
public LRUCache(int capacity) {
this.linkedHashMap = new LinkedHashMap(capacity);
}
class LinkedHashMap {
class Node {
private Node prev;
private Node next;
private int key;
private int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private int capacity;
private Map<Integer, Node> map;
private Node head;
private Node tail;
private int size;
public LinkedHashMap(int capacity) {
this.capacity = capacity;
map = new ConcurrentHashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
size = 0;
}
public synchronized int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node curr = map.get(key);
// remove node
remove(curr);
// insert after head
insertHead(curr);
return curr.value;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void insertHead(Node node) {
Node nextNode = head.next;
head.next = node;
node.prev = head;
node.next = nextNode;
nextNode.prev = node;
}
public synchronized void put(int key, int value) {
Node curr = null;
if (map.containsKey(key)) {
// update value & position
curr = map.get(key);
curr.value = value;
remove(curr);
} else {
curr = new Node(key, value);
map.put(key, curr);
size++;
}
if (size > capacity) {
Node lastNode = tail.prev;
map.remove(lastNode.key);
remove(lastNode);
size--;
}
insertHead(curr);
}
}
public int get(int key) {
return linkedHashMap.get(key);
}
public void put(int key, int value) {
linkedHashMap.put(key, value);
}
}
[1ST TRY]
LintCode
不是很难 关键是doubly linked list在head 和tail 都应该加dummy node
会比不加简洁一万倍
一个是get之后也要update位置
一个是尽管set到同样key的值，value也有可能被改变， 所以也要update位置
public class Solution {
private class Node {
public Node prev, next;
public int key, value;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
private Node head, tail;
private Map<Integer, Node> hash;
private int cap;
// @param capacity, an integer
public Solution(int capacity) {
// write your code here
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
this.hash = new HashMap<Integer, Node>();
this.cap = capacity;
}
// @return an integer
public int get(int key) {
// write your code here
if (!hash.containsKey(key)) return -1;
Node curr = hash.get(key);
moveToTail(curr);
return curr.value;
}
private void moveToTail(Node node) {
//delete node from the current position
node.prev.next = node.next;
node.next.prev = node.prev;
//insert node before tail
tail.prev.next = node;
node.prev = tail.prev;
tail.prev = node;
node.next = tail;
}
// @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
// write your code here
if (hash.containsKey(key)) {
Node curr = hash.get(key);
curr.value = value;
moveToTail(curr);
return;
}
if (hash.size() >= cap) {
hash.remove(head.next.key);
head.next = head.next.next;
head.next.prev = head;
}
Node newNode = new Node(key, value);
hash.put(key, newNode);
tail.prev.next = newNode;
newNode.prev = tail.prev;
tail.prev = newNode;
newNode.next = tail;
}
}
二刷 LeetCode
35.23 %
对doublyLinkedList的处理完全用函数了 感觉还是比较简洁的
写了1个typo Initialize时候tail.prev = head
2个bug 问题出在 每一个node不光要记住它的value 同时也要记住它的key 因为从head remove的时候，需要根据head.next找到hashmap里面的key并删除 所以node要有key和value
class doublyListNode {
public doublyListNode prev, next;
public int key, val;
public doublyListNode(int key, int val) {
this.key = key;
this.val = val;
prev = null;
next = null;
}
}
public class LRUCache {
private doublyListNode head;
private doublyListNode tail;
private int capacity;
private Map<Integer, doublyListNode> map;
public LRUCache(int capacity) {
head = new doublyListNode(-1, -1);
tail = new doublyListNode(-1, -1);
this.capacity = capacity;
map = new HashMap<Integer, doublyListNode>();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
doublyListNode curr = map.get(key);
moveToTail(curr);
return curr.val;
}
public void put(int key, int value) {
doublyListNode curr;
if (map.containsKey(key)) {
curr = map.get(key);
curr.val = value;
moveToTail(curr);
} else {
if (capacity == 0) {
//System.out.println(head.next.key);
map.remove(head.next.key);
deleteFromHead();
capacity++;
}
curr = new doublyListNode(key, value);
map.put(key, curr);
addToTail(curr);
capacity--;
}
}
private void addToTail(doublyListNode node) {
tail.prev.next = node;
node.prev = tail.prev;
node.next = tail;
tail.prev = node;
}
private void deleteFromHead() {
//Empty list
if (head == tail) return;
//Otherwise there are at least 3 nodes
head.next.next.prev = head;
head.next = head.next.next;
}
private void moveToTail(doublyListNode node) {
//delete from list
node.prev.next = node.next;
node.next.prev = node.prev;
//addToTail
addToTail(node);
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
No comments:
Post a Comment