Leetcode(Medium) 146. LRU Cache (Python)

December 4, 2022 程式語言

LRU Cache算是我遇過覺得蠻有趣生活化的題目，感覺也是在很多底層系統會需要用到的觀念。可惜的是目前工作還沒使用到...

純粹紀錄解題方法

題目

🔗

設計一個資料結構符合 Least Recently Used (LRU) cache 機制。

觀念

🔗

快取機制主要就是會保留較常使用的資料，淘汰不常使用的資料，以讓使用者在執行程式時，可以更加快速取得自己想要的資訊。

利用HashMap與DoubleLinkedList搭配實作，
每個事件代表HashMap的key與value，value則是以DoubleLinkedList產生的node，
這樣就能知道node實際的順序。

為了在呼叫 get 與 put 同時更新node的狀態，需要額外有兩個functions輔助
def insertInToHead(self, node):
插入此節點至LinkedList的第一個位置(head的後方、原本第一個節點的前方)

def removeNode(self, node):
移除此節點(前後節點相連)

後續不管是get 與 put，在更改node的狀態時都是使用這兩個functions。

細節

🔗

LRUCache 初始資料結構需包含dummyHead與dummyTail，這樣才能知道最常使用的位置(dummyHead的後一個)與最不常使用的位置(dummyTail的前一個)
呼叫functions put 時，若最終HashMap長度大於capacity，需先刪除HashMap中的值(key:value)，key的value為LinkedList的最後一個節點(dummyTail的前方節點)，再刪除此節點。

程式碼

🔗

Python
class LinkListed:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.size = capacity
        self.dic = {}
        self.dummyHead = LinkListed(0, 0)
        self.dummyTail = LinkListed(0, 0)
        self.dummyHead.next = self.dummyTail
        self.dummyTail.prev = self.dummyHead.next

    def get(self, key: int) -> int:
        if key not in self.dic: return -1
        node = self.dic[key]
        self.removeNode(node)
        self.insertInToHead(node)
        return node.val
        
    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            node = self.dic[key]
            node.val = value
            self.removeNode(node)
            self.insertInToHead(node)
        else:
            node = LinkListed(key, value)
            self.dic[key] = node
            self.insertInToHead(node)
            
            if len(self.dic) > self.size:
                del self.dic[self.dummyTail.prev.key]
                self.removeNode(self.dummyTail.prev)
        
    def insertInToHead(self, node):
        node.next = self.dummyHead.next
        self.dummyHead.next.prev = node
        self.dummyHead.next = node
        node.prev = self.dummyHead
        return
        
    def removeNode(self, node):
        node.next.prev = node.prev
        node.prev.next = node.next
        return