---
# System prepended metadata

title: '**Leetcode筆記(LRU Cache)**'
tags: [linked list, medium, microsoft, leetcode]

---

# **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`