力ボタンブラシ問題146.LRUキャッシュメカニズム(java)
19517 ワード
タイトル
あなたが把握しているデータ構造を運用し、LRU(最近最も少ない使用)キャッシュメカニズムを設計し、実現します.データgetの取得とデータputの書き込みをサポートする必要があります.
取得データget(key)-キー(key)がキャッシュに存在する場合、キーの値(常に正数)が取得され、そうでない場合は-1が返されます.データput(key,value)-キーが存在しない場合は、データ値が書き込まれます.キャッシュ容量が上限に達した場合、新しいデータを書き込む前に、最近最も少ないデータ値を削除して、新しいデータ値にスペースを残す必要があります.
ステップ:
O(1)時間の複雑さの中でこの2つの操作を完了できますか?
例:
構想
ハッシュテーブル+双方向チェーンテーブルhashtable保証get putメソッドがO(1)水平双方向チェーンテーブル保証LRUに達するメカニズム
LinkedahashMap
参照先:https://leetcode-cn.com/problems/lru-cache/solution/lru-huan-cun-ji-zhi-by-leetcode/
あなたが把握しているデータ構造を運用し、LRU(最近最も少ない使用)キャッシュメカニズムを設計し、実現します.データgetの取得とデータputの書き込みをサポートする必要があります.
取得データget(key)-キー(key)がキャッシュに存在する場合、キーの値(常に正数)が取得され、そうでない場合は-1が返されます.データput(key,value)-キーが存在しない場合は、データ値が書き込まれます.キャッシュ容量が上限に達した場合、新しいデータを書き込む前に、最近最も少ないデータ値を削除して、新しいデータ値にスペースを残す必要があります.
ステップ:
O(1)時間の複雑さの中でこの2つの操作を完了できますか?
例:
LRUCache cache = new LRUCache( 2 /* */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 1
cache.put(3, 3); // 2
cache.get(2); // -1 ( )
cache.put(4, 4); // 1
cache.get(1); // -1 ( )
cache.get(3); // 3
cache.get(4); // 4
構想
ハッシュテーブル+双方向チェーンテーブルhashtable保証get putメソッドがO(1)水平双方向チェーンテーブル保証LRUに達するメカニズム
import java.util.Hashtable;
class LRUCache {
//
private class DLinkedNode{
int key ;
int value;
DLinkedNode prev;
DLinkedNode next;
}
//
private void addNode(DLinkedNode node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
//
private void removeNode(DLinkedNode node){
DLinkedNode prev = node.prev;
DLinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
//
private void moveToHead(DLinkedNode node){
removeNode(node);
addNode(node);
}
//
private DLinkedNode popTail(){
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
//
// head tail
private DLinkedNode head,tail;
private int size;
private int capacity;
// hashtable get put O(1)
private Hashtable<Integer,DLinkedNode> cache = new Hashtable<>();
//
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode dLinkedNode = cache.get(key);
if(dLinkedNode == null) return -1;
moveToHead(dLinkedNode);
return dLinkedNode.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null){
DLinkedNode dLinkedNode = new DLinkedNode();
dLinkedNode.key = key;
dLinkedNode.value = value;
cache.put(key,dLinkedNode);
addNode(dLinkedNode);
++ size;
if(size > capacity){
DLinkedNode tail = popTail();
cache.remove(tail.key);
--size;
}
}else{
node.value = value;
moveToHead(node);
}
}
}
LinkedahashMap
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
/**
* LRUCache :
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
参照先:https://leetcode-cn.com/problems/lru-cache/solution/lru-huan-cun-ji-zhi-by-leetcode/