Problem 1 LRU cache
https://leetcode.com/problems/lru-cache/
have been updated to new version
What is cache
为了不每次都重新检索，所先把检索的结果存下来，下次用户访问的时候直接给存好的检索结果
想到的是Map<key, value>, get a key by O(1)
look up operation(memo)，如果计算过了，get上次计算的过，否则就重新算一遍
Cache 的本质就是map，只不过区别是，他是一个有capacity的map
What is used:
所有的增改查insert, update query都是used
put operation == insert/ update
get operation == query
remove operation == delete
注意，很多时候改，以为着是删/增
数据结构界的打工人：Map
Look up something（找什么，就是你所储存的东西） by something(透过什么来找，这个就是key)
经典的Use Case: 我需要知道我自己定义的Entry Reference在哪里，但是我propose的结果不具备优秀的查找功能
Map<Key, Entry Reference> locationMap
key通过什么找reference，Entry Reference你其他的数据结构储存
Example： Array Based PriorityQueue Update(key) Function
Map<key, index> indexMapForKeyinHeap + Heap
所有的操作，只要给我一个Key我都是可以拿到Entry Node, 又有了可以对时间排序的TreeSet/TreeMap
Summary
hybrid注意data structure, 先考虑每个元素cell里面有什么：
cell{key, value, index(hidden)}
再注意，多加结构的时候，必须用cell来做一个单位，会让思路更简单，比如说这道题如果用treeSet
map(key, cell) && container(cell)
并不能用map(key, index) && container(cell) , and Cell only have{key, index} ，why???
因为如果你需要知道这个元素里的其他资料
/*
Clarification:
- get
- given key, to see value
- return the value
- put
- given key, to edit value
- update key access order(arbitrary)
- update key's value ==> update value(look up)
- if key is in?
- remove from container& map
- insert
- append()
- if the cache limit is not reach && key not in?
- insert(K, V)
- put the element into the access order ==> append()
- if the cache limit is reach && key in?
- delete() LRU element => deleteMin() (access order) & remove from map
- insert(K, V)
- append()
High Level:
- we need a ds to maintain the access order --- find a sorted order sorted
- Map + TreeSet
Middle Level:
- Unsorted? Map/ set
- map? Key, value? O(1)
- Pop? Check all then pop , O (n)
- Half sorted? TreeMap, heap
- container(element),Element sorted by index?
- Map<key/element,value>?
- Sorted ? List? Doublelinkedlist
- Element? Key,value, element
- Linkedlist<element>
- Map<element, index>
TC& SC
*/
Method 1 TreeSet/ TreeMap + Map
Step 1 Use Case API design
Step 2: Detail Logic
get(key):
case 1 : map 里面有这个key
透过Map拿到Entry node（return的data就在里面）
update这个Entry Node的时间信息（TreeSet里的这个Entry做update--> delete + insert）
case 2: map里面没有这个key
return null
overall: O(logn)
put(key, value):
case 1: map 里面有这个key
想当于update这个key-value pair里的value
通过Map拿到Entry Node
update 这个Entry Node的value信息
update 这个Entry Node的时间信息
case 2: map 里面没有这个key
case 2.1 现在没有满
直接放一个新的Entry（update two maps）
case 2.2 现在满了
踢出一个leat recently used：也就是TreeSet里面时间戳
overall: O(logn)
timeStamp:
设计为当前LRU class里的一个feild
updated 准则，任何operation都需要update当前的信息
capacity:
设计为当前LRU class的一个field
注意put的details操作
FYI
Timestamp today = new Timestamp(System.currentTimeMillis())
TreeSet Version
// Some code
// not correct
```java
```java
class LRUCache {
private final int CAPACITY;
private int timeStamp;
private TreeSet<Entry> treeSet;
private Map<Integer, Entry> map;
public LRUCache(int capacity) {
// assume cap valid
this.CAPACITY = capacity;
this.map = new HashMap<>();
this.treeSet = new TreeSet<>();
this.timeStamp = 0;
}
private void updateTimeStamp() {
this.timeStamp++;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Entry cur = map.get(key);
treeSet.remove(cur);
updateTimeStamp();
cur.timeStamp = this.timeStamp;
treeSet.add(cur);
System.out.println(cur.value);
return cur.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Entry cur = map.get(key);
treeSet.remove(cur);
updateTimeStamp();
cur.timeStamp = this.timeStamp;
cur.value = value;
treeSet.add(cur);
return;
}
else {
updateTimeStamp();
Entry newEntry = new Entry(key, value, timeStamp);
if (treeSet.size() == CAPACITY) {
Entry leastRecentUsedEntry = treeSet.first();
treeSet.remove(leastRecentUsedEntry);
map.remove(leastRecentUsedEntry.key);
}
map.put(key, newEntry);
treeSet.add(newEntry);
}
}
class Entry implements Comparable<Entry> {
int timeStamp;
int key;
int value;
public Entry(int key, int value, int timeStamp) {
this.timeStamp = timeStamp;
this.key = key;
this.value = value;
}
@Override
public int compareTo(Entry other) {
return Integer.compare(this.timeStamp, other.timeStamp);
}
}
}
// class LRUCache {
// class Cell implements Comparable<Cell>{
// int key;
// int val;
// int index;
// Cell(int key, int val, int index) {
// this.key = key;
// this.val= val;
// this.index = index;
// }
// @Override
// public int compareTo(Cell that) {
// int result = Integer.compare(this.index, that.index);
// int result_b = Integer.compare(this.key, that.key);
// if (result == 0) {
// return result_b;
// }
// return result;
// }
// }
// HashMap<Integer, Cell> map; // key -> Cell
// TreeSet<Cell> minSet; // key, Cell
// int count;
// int capacity;
// public LRUCache(int capacity) {
// this.capacity = capacity;
// map = new HashMap<>();
// minSet = new TreeSet<>();
// }
// public int get(int key) {
// Cell cur = map.get(key);
// if (cur == null) {
// return -1;
// }
// int value = cur.val;
// minSet.remove(cur);
// count++;
// Cell newCur = new Cell(key, value, count);
// minSet.add(newCur);
// map.put(key, newCur);
// return value;
// }
// public void put(int key, int value) {
// Cell cur = map.get(key);
// count++;
// if (cur != null) {
// minSet.remove(cur);
// map.remove(cur);
// }
// else if (cur == null && map.size() == capacity) {
// Cell needRemove = minSet.pollFirst();
// map.remove(needRemove.key);
// }
// Cell curNew = new Cell(key, value, count);
// minSet.add(curNew);
// map.put(key, curNew);
// }
// }
TreeMap Version
// Some code
class LRUCache {
// treeMap version
private final int CAPACITY;
private int timeStamp;
private Map<Integer, Integer> cache;
private TreeMap<Integer, Entry> timeOrder; // TreeMap key is timeStamp
public LRUCache(int capacity) {
this.timeStamp = -1;
this.cache = new HashMap<>();
this.timeOrder = new TreeMap<>();
this.CAPACITY = capacity;
}
public int get(int key) {
if (cache.containsKey(key)) {
Integer timeStamp = cache.get(key);
Entry pair = timeOrder.get(timeStamp);
increaseTimeStamp();
updateTimeOrder(timeStamp, pair);
return pair.getValue();
}
else {
return -1;
}
}
private void increaseTimeStamp() {
this.timeStamp++;
}
private int getTimeStamp(){
return this.timeStamp;
}
private int getCap() {
return this.CAPACITY;
}
private void evictOldest(int time){
Entry old = timeOrder.get(time);
this.timeOrder.remove(time);
this.cache.remove(old.getKey());
}
private void updateTimeOrder(int timeStamp, Entry pair) {
evictOldest(timeStamp);
timeOrder.put(getTimeStamp(), pair);
cache.put(pair.getKey(), getTimeStamp());
}
private void addToCache(int currentTime, Entry pair) {
timeOrder.put(currentTime, pair);
cache.put(pair.getKey(), currentTime);
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
Integer timeStamp = cache.get(key);
Entry pair = timeOrder.get(timeStamp);
pair.setValue(value);
increaseTimeStamp();
updateTimeOrder(timeStamp,pair);
}
else {
Entry pair = new Entry(key, value);
increaseTimeStamp();
int time = getTimeStamp();
if (isEmpty()) {
addToCache(time, pair);
return;
}
if (isFull()) {
Integer oldestPairTimeStamp = timeOrder.firstKey();
evictOldest(oldestPairTimeStamp);
}
addToCache(time, pair);
}
}
public boolean isFull() {
return getSize() == getCap();
}
public boolean isEmpty() {
return getSize() == 0;
}
private int getSize() {
return this.cache.size();
}
class Entry {
private int key;
private int value;
public Entry(int key, int value) {
this.key = key;
this.value = value;
}
public int getKey() {
return this.key;
}
public int getValue() {
return this.value;
}
public void setKey(int key) {
this.key = key;
}
public void setValue(int value) {
this.value = value;
}
}
}
```Method 2 DoubleLinkedList
除了treeSet还有什么数据结构可以保持时间顺序？ Queue==> FIFO时间顺序
Queue逻辑上的数据结构 => 怎么实现Queue
Queue<Integer> queue = new ArrayDeque<>();
Queue<Integer> queue = new LinkedList<>();
增删改查全是O(1)
Queue是逻辑数据结构，底层实现的是LinkedList
而DoubleLinkedList是因为O(1)的删除
那你得给我这个node reference，有了这个node reference,我做什么都是O(1),关键问题是，人家User insert/update/remove/query，人家给你的是key，不是node reference
打工人上线: Map<Key, DoublyListNode> locationMap + DoubleLinkedList(datainfo) DLL
Step 1 Use Case API design
get(key)
put(key, value)
Step 2: Detail Logic
get(key):
case 1 : map 里面有这个key
get the key==> 通过map拿到装有data的ListNode ==> ListNode里面的东西就是return的东西
update time order ==> remove this ListNode from LinkedList, then insert into Head
case 2: map里面没有这个key
return null
overall: O(logn)
put(key, value):
case 1: map 里面有这个key
update the value ==> 通过map拿到装有data的ListNode ==》 update ListNode
update the order ==> remove this ListNode from LinkedList, then insert into head
case 2: map 里面没有这个key
case 2.1 the cache is not full (check map 的size到不到capacity)
put the key value there
update the time order ==> insert into Head
case 2.2 现在满了
delete the oldest one ==> 踢出tail node
put the kye value there ==> insert into map and LL
update the time order ==> head
overall: O(1)
timeStamp:
设计为当前LRU class里的一个feild
updated 准则，任何operation都需要update当前的信息
capacity
设计为当前LRU class的一个field
import static java.lang.Math.nextDown;
/*
Element: <key, value, timeStamp>
<key, Element>
<Element_1> --> <Element_2>
get: given a key to see if we can find the value in the container(using the lookupMap check)
in? find this element, rand update its timeStamp, put it back
not? reutrn -1
put: given a key and value
- container this key, find this element, update its value& timeStamp, and put it back
- not container,
- if reach the capacity, delete the least element
- put this element into the container
*/
class LRUCache {
// class Node implements Comparable<Node> {
class Node {
int key;
int value;
int timeStamp;
Node prev;
Node next;
// public Node (int key, int value, int timeStamp) {
public Node (int key, int value) {
this.key = key;
this.value = value;
// this.timeStamp = timeStamp;
}
// @Override
// public int compareTo(Node that) {
// return Integer.compare(this.timeStamp, that.timeStamp);
// }
}
private Node head;
private Node tail;
private Map<Integer, Node> map;
private final int CAPACITY;
public LRUCache(int capacity) {
this.CAPACITY = capacity;
this.map = new HashMap<>();
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node cur = map.get(key);
deleteNode(cur);
addNode(cur);
return cur.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node cur = map.get(key);
cur.value = value;
deleteNode(cur);
addNode(cur);
} else {
if (map.size() == this.CAPACITY) {
deleteNode(tail);
}
addNode(new Node(key, value));
}
}
private void deleteNode(Node node) {
map.remove(node.key);
if (node.prev != null && node.next != null) {
Node prevNode = node.prev;
Node nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
else if (node.prev == null && node.next != null) { // node = head, more than 2 node
head = node.next;
head.prev = null;
}
else if (node.prev != null && node.next == null) { // node = tail, more than 2 node
tail = node.prev;
tail.next = null;
} else { // node = head = tail, only 1 element
head = tail = null;
}
node.prev = node.next = null;
}
private void addNode(Node node) {
map.put(node.key, node);
if (head == null) {
head = tail = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
}
}
```Last updated