# **Leetcode筆記(LRU Cache)**
:::info
:information_source: 題目 : LRU Cache, 類型 : linked list , 等級 : medium
日期 : 2023/05/30，2023/07/03，2023/11/19，2024/10/05
:::
### 嘗試
加油加油，微軟題目!!
要建立一個double linked list，因為這樣才可以確保同時找的到前面和後面的node
-> A double-linked list allows for efficient removal and insertion operations in constant time (O(1))
linked list的部分
-> 用right和left去控制最左跟最右，其他剩下的node夾在中間
-> get(取數字) 優先順序會提升 所以要先remove再insert
-> put(加數字) 同時加在hashmap跟鍊表，如果超出capacity則刪除左邊的
hashmap的部分
-> hashmap[key] = Node(key, value)
-> 用來記錄這個node到底有沒有存在
2023/07/03
```python
# double linked list
class Node:
def __init__(self, key = 0, val = 0):
self.key, self.val = key, val
self.next, self.pre = None, None # ->是next <-是pre
class LRUCache:
def __init__(self, capacity: int):
self.hashmap = {} # hashmap[key] = Node(key, value)
self.capacity = capacity
self.left, self.right = Node(), Node()
self.left.next, self.right.pre = self.right, self.left
def remove(self, node):
# 用自己的left right去操作
l, r = node.pre, node.next
l.next, r.pre = r, l
def insert(self, node):
# 總是加到最右邊
l = self.right.pre
l.next, self.right.pre = node, node
node.pre, node.next = l, self.right
def get(self, key: int) -> int:
# 鍊表 : 如果key存在 那就先刪除它再加入它(改優先順序)
# 字典 : 如果存在不用動 只是要取值而已
if key in self.hashmap:
self.remove(self.hashmap[key])
self.insert(self.hashmap[key])
return self.hashmap[key].val
return -1
def put(self, key: int, value: int) -> None:
# 加東西
# 鍊表 : 一律刪除再更新(數值可能變)
# 字典 : 不用管 更新就對了
if key in self.hashmap:
self.remove(self.hashmap[key])
self.hashmap[key] = Node(key, value) # 字典
self.insert(self.hashmap[key]) # 鍊表
# 超過了 刪掉最左的
if len(self.hashmap) > self.capacity:
lru = self.left.next
del self.hashmap[lru.key]
self.remove(lru)
```
2023/11/19
```python
class ListNode:
def __init__(self, val, key, post=None, pre=None):
self.val = val
self.key = key
self.post = post
self.pre = pre
class LinkedList:
def __init__(self, R, L):
self.L = L
self.R = R
self.L.post = self.R
self.R.pre = self.L
self.size = 0
def delete(self, node):
left, right = node.pre, node.post
if left is not None:
left.post = right
if right is not None:
right.pre = left
del node
self.size -= 1
def add(self, node):
# always add on the right hand side
left = self.R.pre
left.post, self.R.pre = node, node
node.post, node.pre = self.R, left
self.size += 1
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.record = dict() # dict[key] = Node(key, val)
self.R, self.L = ListNode(0, 0), ListNode(0, 0)
self.linked = LinkedList(self.R, self.L)
def get(self, key: int) -> int:
if key in self.record:
self.linked.delete(self.record[key])
self.linked.add(self.record[key])
return self.record[key].val
return -1
def put(self, key: int, value: int) -> None:
if key in self.record:
self.linked.delete(self.record[key]) # remove the old one
self.record[key] = ListNode(value, key)
self.linked.add(self.record[key])
if self.linked.size > self.capacity:
left = self.L.post
self.linked.delete(left)
del self.record[left.key]
```
2023/11/24
記得double linked list是要指向node
```python
class Node:
def __init__(self, key = 0, val = 0, prev = None, post = None):
self.key = key
self.val = val
self.prev = prev
self.post = post
class LinkedList:
def __init__(self):
self.R, self.L = Node(), Node()
self.L.post = self.R
self.R.prev = self.L
def add(self, node):
# l <-> R
# l <-> node <-> R
l = self.R.prev
l.post, self.R.prev = node, node
node.prev, node.post = l, self.R
def delete(self, node):
# l <-> node <-> r
# l <-> r
l, r = node.prev, node.post
if l and r:
l.post, r.prev = r, l
del node
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.hashmap = dict() # key : double linked list
self.dLinkedList = LinkedList() #
def get(self, key: int) -> int:
if key in self.hashmap:
self.dLinkedList.delete(self.hashmap[key])
self.dLinkedList.add(self.hashmap[key])
return self.hashmap[key].val
return -1
def put(self, key: int, value: int) -> None:
if key in self.hashmap:
self.dLinkedList.delete(self.hashmap[key])
self.hashmap[key] = Node(key, value)
self.dLinkedList.add(self.hashmap[key])
if len(self.hashmap) > self.capacity:
node = self.dLinkedList.L.post
self.dLinkedList.delete(node)
del self.hashmap[node.key]
```
2023/12/09
```python
"""
L->2->3<->1<->R
class Node():
key, val : indicator
pre, post : pointer
class DLL():
R, L : boundary
add : on right
delete : on left
class LRUCache():
hashmap : dict (key (key) : value (Node))
DLL : store hashamp[key]
"""
class Node():
def __init__(self, key = 0, val = 0):
self.key = key
self.val = val
self.pre = None
self.post = None
class DLL():
def __init__(self):
self.R = Node()
self.L = Node()
self.R.pre = self.L
self.L.post = self.R
def add(self, node):
# temp <-> R
# temp <-> node <-> R
temp = self.R.pre
temp.post = node
self.R.pre = node
node.pre, node.post = temp, self.R
def delete(self, node):
# temp_l <-> node <-> temp_r
# temp_l <-> temp_r
temp_l, temp_r = node.pre, node.post
temp_l.post = temp_r
temp_r.pre = temp_l
class LRUCache(object):
def __init__(self, capacity):
self.cap = capacity
self.dll = DLL() # store hashamp[key]
self.hashmap = dict() # key (key) : value (Node)
def get(self, key):
if key in self.hashmap:
self.dll.delete(self.hashmap[key])
self.dll.add(self.hashmap[key])
return self.hashmap[key].val
return -1
def put(self, key, value):
if key in self.hashmap:
self.dll.delete(self.hashmap[key])
self.hashmap[key] = Node(key, value)
self.dll.add(self.hashmap[key])
if len(self.hashmap) > self.cap:
temp = self.dll.L.post
self.dll.delete(self.hashmap[temp.key])
del self.hashmap[temp.key]
```
2024/10/05
加油，記得當初在面試微軟前，寫到這題，覺得如果面試官問我這題，那真的完蛋。雖然最後面試結果還是沒上，但至少為後來奠定基礎
謝謝當時的自己，現在整個架構熟悉多了
```python
class Node:
def __init__(self, key = -1, val = -1, pre = None, post = None):
self.key = key
self.val = val
self.pre = pre
self.post = post
class DoubleLinkedlist:
def __init__(self):
self.R = Node()
self.L = Node()
self.R.pre = self.L
self.L.post = self.R
def remove(self, node): # node on the linkedlist
# l <-> node <-> r
# l <-> r
l, r = node.pre, node.post
l.post = r
r.pre = l
return
def add(self, node): # add on the right
# l <-> R
# l <-> node <-> R
l = self.R.pre
l.post, self.R.pre = node, node
node.pre, node.post = l, self.R
return
class LRUCache:
def __init__(self, capacity: int):
self.record = {} # key : Node
self.dl = DoubleLinkedlist()
self.capacity = capacity
def get(self, key: int) -> int:
if key in self.record:
node = self.record[key]
self.dl.remove(node)
self.dl.add(node)
return node.val
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.record:
node = self.record[key]
node.val = value
self.dl.remove(node)
self.dl.add(node)
else: # add in cache
if len(self.record) == self.capacity: # reach limit
garbage = self.dl.L.post
self.dl.remove(garbage)
del self.record[garbage.key]
new_node = Node(key, value)
self.dl.add(new_node)
self.record[key] = new_node
return
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
```
---
### **優化**
```python
class Node:
def __init__(self, key, value):
self.key, self.value = key, value
# 雙向指標
self.pre, self.nxt = None, None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {} # cache[key] = Node(key, value)
# 左極點與右極點
# 有寫self代表是全域變數 之後其他函數可以訪問
self.left, self.right = Node(0, 0), Node(0, 0)
self.left.nxt, self.right.pre = self.right, self.left
def remove(self, node):
l, r = node.pre, node.nxt
l.nxt, r.pre = r, l
def insert(self, node):
# 加到右邊
l, r = self.right.pre, self.right
r.pre, l.nxt = node, node
node.pre, node.nxt = l, r
def get(self, key: int) -> int:
# 順便把最新的加到linked list右邊
if key in self.cache:
self.remove(self.cache[key])
self.insert(self.cache[key])
return self.cache[key].value
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.remove(self.cache[key]) # 要update
self.cache[key] = Node(key, value)
self.insert(self.cache[key])
if len(self.cache) > self.cap:
lm = self.left.nxt # node
self.remove(lm)
del self.cache[lm.key] # 徹底刪除
```
---
**:warning: 錯誤語法**
:::warning
:::
**:thumbsup:學習**
:::success
:::
**思路**
**講解連結**
https://www.youtube.com/watch?v=7ABFKPK2hD4&ab_channel=NeetCode
Provided by. Neetcode
###### tags: `linked list` `medium` `leetcode`
Sign in with Wallet
Connect another wallet