2020-10-16

JiayangWu · JiayangWu · commit 719c95796a37 · 2020-10-16T01:20:20.000-04:00
diff --git a/0146.LRU缓存机制/0146-LRU缓存机制.py b/0146.LRU缓存机制/0146-LRU缓存机制.py
@@ -1,41 +1,74 @@
-class LRUCache(object):
+class DLLNode(object):
+    def __init__(self, key, val, pre, nxt):
+        self.key = key
+        self.val = val 
+        self.pre = pre 
+        self.nxt = next
 
+class LRUCache(object):
     def __init__(self, capacity):
         """
         :type capacity: int
         """
-        from collections import OrderedDict
         self.capacity = capacity
-        self.record = OrderedDict()
+        self.size = 0
+        self.head = DLLNode(-1, -1, None, None)
+        self.tail = DLLNode(-1, -1, self.head, None)
+        self.head.next = self.tail 
+        self.dic = dict()
 
     def get(self, key):
         """
         :type key: int
         :rtype: int
         """
-        if key in self.record:
-            tmp = self.record.pop(key)
-            self.record[key] = tmp
-            return tmp
-        else:
+        if key not in self.dic:
             return -1
-        
+        else:
+            value = self.dic[key].val
+            self.moveToHead(self.dic[key])
+            return value 
 
     def put(self, key, value):
         """
         :type key: int
         :type value: int
         :rtype: None
         """
-        if key in self.record:
-            self.record.pop(key)         
-        else:
-            if self.capacity > 0:
-                self.capacity -= 1
+        if key not in self.dic:
+            node = DLLNode(key, value, None, None)
+            self.dic[key] = node
+            if self.size < self.capacity:
+                self.size += 1
             else:
-                self.record.popitem(last = False)
-        self.record[key] = value
+                self.removeLastElement()
+            self.insertToHead(node)
+        else:
+            self.dic[key].val = value
+            self.moveToHead(self.dic[key])
+
+    def insertToHead(self, node):
+
+        pre_first = self.head.next
+        self.head.next = node
+        node.pre = self.head 
+        pre_first.pre = node 
+        node.next = pre_first
         
+        # print (node.key, node.pre.key, node.next.key)
+
+    def removeLastElement(self):
+        pre_last = self.tail.pre 
+        pre_second_last = pre_last.pre
+        pre_second_last.next = self.tail
+        self.tail.pre = pre_second_last
+        self.dic.pop(pre_last.key)
+    
+    def moveToHead(self, node):
+        node.pre.next = node.next
+        node.next.pre = node.pre
+
+        self.insertToHead(node)
 
 
 # Your LRUCache object will be instantiated and called as such:
diff --git a/面试题16.25.LRU缓存/面试题16.25-LRU缓存.py b/面试题16.25.LRU缓存/面试题16.25-LRU缓存.py
@@ -0,0 +1,78 @@
+class DLLNode(object):
+    def __init__(self, key, val, pre = None, next = None):
+        self.key = key
+        self.val = val
+        self.pre = pre
+        self.next = next
+
+class LRUCache(object):
+    def __init__(self, capacity):
+        """
+        :type capacity: int
+        """
+        self.capacity = capacity
+        self.size = 0
+        self.head = DLLNode(-1, -1)
+        self.tail = DLLNode(-1, -1, self.head)
+        self.head.next = self.tail
+        self.dic = {}
+
+    def get(self, key):
+        """
+        :type key: int
+        :rtype: int
+        """
+        if key in self.dic:
+            res = self.dic[key].val
+            self.moveToHead(self.dic[key]) # set this node to be most recently used
+            return res
+        return -1
+
+    def put(self, key, value):
+        """
+        :type key: int
+        :type value: int
+        :rtype: None
+        """
+        if key in self.dic:
+            self.dic[key].val = value
+            self.moveToHead(self.dic[key])
+        else:
+            node = DLLNode(key, value)
+            self.dic[key] = node
+            if self.size < self.capacity:
+                self.size += 1
+            else:
+                self.removeLastNode()
+            self.insertToHead(node)
+        
+    def insertToHead(self, node):
+        pre_first = self.head.next
+        self.head.next = node
+        node.pre = self.head
+        node.next = pre_first
+        pre_first.pre = node
+
+    def moveToHead(self, node):
+        # 1. take it out
+        node.pre.next = node.next
+        node.next.pre = node.pre
+        # 2. insert it to the head
+        self.insertToHead(node)
+
+    def removeLastNode(self):
+        pre_last = self.tail.pre
+        pre_second_last = pre_last.pre
+
+        pre_second_last.next = self.tail
+        self.tail.pre = pre_second_last
+
+        self.dic.pop(pre_last.key)
+                
+
+
+
+# Your LRUCache object will be instantiated and called as such:
+# obj = LRUCache(capacity)
+# param_1 = obj.get(key)
+# obj.put(key,value)
