Leetcode(Medium) 146. LRU Cache (Python)
Just record my solving method of problem
Problem
🔗Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Concept
🔗The main purpose of the cache mechanism is to keep the more frequently used data and eliminate the infrequently used data, so that users can obtain the information they want more quickly when executing the program.
Use HashMap and DoubleLinkedList to implement, Each event represents the key and value of the HashMap, and the value is the node generated by DoubleLinkedList. This way you can know the actual order of the nodes.
In order to update the state of the node while calling functions get and put, two additional functions are required
def insertInToHead(self, node):
Insert this node to the first position of LinkedList (behind the head, in front of the original first node)
def removeNode(self, node):
Remove this node (connect the node of front and back nodes)
Whether it is calling functions get or put, above of two functions are used when changing the state of the node.
Detail
🔗- The initial data structure of LRUCache needs to include dummyHead and dummyTail, so as to know the most frequently used position (the one after dummyHead) and the least frequently used position (the one before dummyTail)
- When calling functions put, if the final HashMap length is greater than capacity, you need to delete the value (key:value) in the HashMap first. The value of the key is the last node of the LinkedList (the node in front of dummyTail), and then delete this node.
Code
🔗Pythonclass 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
Alvin
Software engineer, interested in financial knowledge, health concepts, psychology, independent travel, and system design.
Related Posts
Discussion (0)
No comments yet.