本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
Data Structure
146. LRU 缓存机制
双向链表存储数据状态，哈希表更新数据。
python
class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.key_to_node = defaultdict(int)
self.dummy = Node()
self.dummy.prev = self.dummy
self.dummy.next = self.dummy
def get_node(self, key: int) -> Optional[Node]:
if key not in self.key_to_node:
return None
node = self.key_to_node[key]
self.remove(node)
self.push_front(node)
return node
def get(self, key: int) -> int:
node = self.get_node(key)
return node.value if node else -1
def put(self, key: int, value: int) -> None:
node = self.get_node(key)
if node:
node.value = value
return
self.key_to_node[key] = node = Node(key, value)
self.push_front(node)
if len(self.key_to_node) > self.capacity:
back_node = self.dummy.prev
self.remove(back_node)
del self.key_to_node[back_node.key]
def remove(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def push_front(self, node: Node) -> None:
node.prev = self.dummy
node.next = self.dummy.next
node.prev.next = node
node.next.prev = node
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)java
class LRUCache {
private static class Node {
private int key, value;
private Node prev, next;
Node (int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Node dummy = new Node(0, 0);
private final Map<Integer, Node> keyToNode = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
dummy.prev = dummy;
dummy.next = dummy;
}
public int get(int key) {
Node node = getNode(key);
return node != null ? node.value: -1;
}
public void put(int key, int value) {
Node node = getNode(key);
if (node != null) {
node.value = value;
return;
}
node = new Node(key, value);
keyToNode.put(key, node);
pushFirst(node);
if (keyToNode.size() > capacity) {
Node backNode = dummy.prev;
keyToNode.remove(backNode.key);
remove(backNode);
}
}
private Node getNode(int key) {
if (!keyToNode.containsKey(key)) {
return null;
}
Node node = keyToNode.get(key);
remove(node);
pushFirst(node);
return node;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void pushFirst(Node node) {
node.prev = dummy;
node.next = dummy.next;
node.prev.next = node;
node.next.prev = 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);
*/460. LFU 缓存
双向链表存储数据状态，哈希表更新数据，不同频率的数据存储在不同的双向链表中。
python
class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.freq = 1
class LFUCache:
def __init__(self, capacity: int):
def new_list():
dummy = Node()
dummy.prev = dummy
dummy.next = dummy
return dummy
self.capacity = capacity
self.key_to_node = defaultdict(int)
self.freq_to_dummy = defaultdict(new_list)
def get_node(self, key: int) -> Optional[Node]:
if key not in self.key_to_node:
return None
node = self.key_to_node[key]
self.remove(node)
dummy = self.freq_to_dummy[node.freq]
if dummy.prev == dummy:
del self.freq_to_dummy[node.freq]
if self.min_freq == node.freq:
self.min_freq += 1
node.freq += 1
self.push_front(self.freq_to_dummy[node.freq], node)
return node
def get(self, key: int) -> int:
node = self.get_node(key)
return node.value if node else -1
def put(self, key: int, value: int) -> None:
node = self.get_node(key)
if node:
node.value = value
return
if len(self.key_to_node) == self.capacity:
dummy = self.freq_to_dummy[self.min_freq]
back_node = dummy.prev
del self.key_to_node[back_node.key]
self.remove(back_node)
if dummy.prev == dummy:
del self.freq_to_dummy[self.min_freq]
self.key_to_node[key] = node = Node(key, value)
self.min_freq = 1
self.push_front(self.freq_to_dummy[self.min_freq], node)
def remove(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def push_front(self, dummy: Node, node: Node) -> None:
node.prev = dummy
node.next = dummy.next
node.prev.next = node
node.next.prev = node
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)java
class LFUCache {
private static class Node {
private int key, value, freq = 1;
private Node prev, next;
Node (int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> keyToNode = new HashMap<>();
private final Map<Integer, Node> freqToDummy = new HashMap<>();
private int minFreq;
public LFUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
Node node = getNode(key);
return node != null ? node.value: -1;
}
public void put(int key, int value) {
Node node = getNode(key);
if (node != null) {
node.value = value;
return;
}
if (keyToNode.size() == capacity) {
Node dummy = freqToDummy.get(minFreq);
Node backNode = dummy.prev;
keyToNode.remove(backNode.key);
remove(backNode);
if (dummy.prev == dummy) {
freqToDummy.remove(minFreq);
}
}
node = new Node(key, value);
keyToNode.put(key, node);
minFreq = 1;
pushFirst(minFreq, node);
}
private Node getNode(int key) {
if (!keyToNode.containsKey(key)) {
return null;
}
Node node = keyToNode.get(key);
remove(node);
Node dummy = freqToDummy.get(node.freq);
if (dummy.prev == dummy) {
freqToDummy.remove(node.freq);
if (minFreq == node.freq) {
minFreq++;
}
}
pushFirst(++node.freq, node);
return node;
}
private Node newList() {
Node dummy = new Node(0, 0);
dummy.prev = dummy;
dummy.next = dummy;
return dummy;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void pushFirst(int freq, Node node) {
Node dummy = freqToDummy.computeIfAbsent(freq, k -> newList());
node.prev = dummy;
node.next = dummy.next;
node.prev.next = node;
node.next.prev = node;
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/1206. 设计跳表
python
class SkiplistNode():
def __init__(self, val: int, max_level=32):
self.val = val
self.forward = [None] * max_level
class Skiplist:
max_level = 32
p_factor = 0.5
def __init__(self):
self.head = SkiplistNode(-1)
self.level = 0
def random_level(self):
level = 1
while level < self.max_level and random.random() < self.p_factor:
level += 1
return level
def search(self, target: int) -> bool:
cur = self.head
for i in range(self.level - 1, -1, -1):
while cur.forward[i] and cur.forward[i].val < target:
cur = cur.forward[i]
cur = cur.forward[0]
return cur is not None and cur.val == target
def add(self, num: int) -> None:
update = [self.head] * self.max_level
cur = self.head
for i in range(self.level - 1, -1, -1):
while cur.forward[i] and cur.forward[i].val < num:
cur = cur.forward[i]
update[i] = cur
level = self.random_level()
self.level = max(self.level, level)
node = SkiplistNode(num, level)
for i in range(level):
node.forward[i] = update[i].forward[i]
update[i].forward[i] = node
def erase(self, num: int) -> bool:
update = [None] * self.max_level
cur = self.head
for i in range(self.level - 1, -1, -1):
while cur.forward[i] and cur.forward[i].val < num:
cur = cur.forward[i]
update[i] = cur
cur = cur.forward[0]
if cur is None or cur.val != num:
return False
for i in range(self.level):
if update[i].forward[i] != cur:
break
update[i].forward[i] = cur.forward[i]
while self.level > 1 and self.head.forward[self.level - 1] is None:
self.level -= 1
return True
# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)java
class SkiplistNode {
int val;
SkiplistNode[] forward;
public SkiplistNode(int val, int maxLevel) {
this.val = val;
this.forward = new SkiplistNode[maxLevel];
}
}
class Skiplist {
int level = 0;
int maxLevel = 32;
SkiplistNode head = new SkiplistNode(-1, maxLevel);
private int randomLevel() {
int lv = 1;
Random random = new Random();
while (lv < maxLevel && random.nextInt(2) == 0) {
lv++;
}
return lv;
}
public boolean search(int target) {
SkiplistNode cur = head;
for (int i = level - 1; i >= 0; i--) {
while (cur.forward[i] != null && cur.forward[i].val < target) {
cur = cur.forward[i];
}
}
cur = cur.forward[0];
return cur != null && cur.val == target;
}
public void add(int num) {
SkiplistNode[] update = new SkiplistNode[maxLevel];
SkiplistNode cur = head;
for (int i = level - 1; i >= 0; i--) {
while (cur.forward[i] != null && cur.forward[i].val < num) {
cur = cur.forward[i];
}
update[i] = cur;
}
int lv = randomLevel();
if (lv > level) {
for (int i = level; i < lv; i++) {
update[i] = head;
}
level = lv;
}
SkiplistNode node = new SkiplistNode(num, lv);
for (int i = 0; i < lv; i++) {
node.forward[i] = update[i].forward[i];
update[i].forward[i] = node;
}
}
public boolean erase(int num) {
SkiplistNode[] update = new SkiplistNode[maxLevel];
SkiplistNode cur = head;
for (int i = level - 1; i >= 0; i--) {
while (cur.forward[i] != null && cur.forward[i].val < num) {
cur = cur.forward[i];
}
update[i] = cur;
}
cur = cur.forward[0];
if (cur == null || cur.val != num) {
return false;
}
for (int i = 0; i < level && update[i].forward[i] == cur; i++) {
update[i].forward[i] = cur.forward[i];
}
while (level > 0 && head.forward[level - 1] == null) {
level--;
}
return true;
}
}
/**
* Your Skiplist object will be instantiated and called as such:
* Skiplist obj = new Skiplist();
* boolean param_1 = obj.search(target);
* obj.add(num);
* boolean param_3 = obj.erase(num);
*/