同步操作将从 陌溪/LearningNotes 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
# 双向Listclass Node(object):def __init__(self, val=None, key=None, left=None, right=None):# 键self.key = key# 值self.val = valself.left = leftself.right = rightclass LRUCache(object):def __init__(self, capacity):self.capacity = capacityself.map = {}self.array = []self.size = 0self.root = Nonedef get(self, key):if self.map.get(key):node = self.map.get(key)# 判断要删除的是不是根节点if key != self.root.key:# 移除使用的节点,将其移动到最后leftNode = node.leftrightNode = node.rightleftNode.right = rightNoderightNode.left = leftNode# 将该节点放到最后leftRoot = self.root.leftleftRoot.right = nodenode.left = leftRootnode.right = self.rootself.root.left = nodereturn node.valelse:leftNode = node.leftrightNode = node.rightleftNode.right = rightNoderightNode.left = leftNode# 将该节点放到最后leftRoot = self.root.leftrightRoot = self.root.rightleftRoot.right = nodenode.left = leftRootnode.right = rightRootself.root = rightRootreturn node.valelse:return -1def put(self, key, value):if self.size < self.capacity:if self.size == 0:# 插入的是第一个节点,那么就是root节点,双向循环链表node = Node()node.key = keynode.val = valuenode.left = nodenode.right = nodeself.root = nodeself.map[key] = nodeself.size += 1elif self.map.get(key):# 将该元素移动到最新使用的node = self.map.get(key)node.val = value# 判断要删除的是不是根节点if key != self.root.key:# 移除使用的节点,将其移动到最后leftNode = node.leftrightNode = node.rightleftNode.right = rightNoderightNode.left = leftNode# 将该节点放到最后leftRoot = self.root.leftleftRoot.right = nodenode.left = leftRootnode.right = self.rootself.root.left = nodeself.map[key] = nodeelse:leftNode = node.leftrightNode = node.rightleftNode.right = rightNoderightNode.left = leftNode# 将该节点放到最后leftRoot = self.root.leftrightRoot = self.root.rightleftRoot.right = nodenode.left = leftRootnode.right = rightRootself.root = rightRootself.map[key] = node# # 将该元素移动到最新使用的# node = self.map.get(key)# # 更新元素中的值# node.val = value# node.key = key# # 移除使用的节点,将其移动到最后# leftNode = node.left# rightNode = node.right# leftNode.right = rightNode# rightNode.left = leftNode## # 将该节点放到最后# leftRoot = self.root.left# leftRoot.left = node# node.left = leftRoot# node.right = self.root# self.root.left = nodeelse:leftRoot = self.root.leftnode = Node()node.val = valuenode.key = keynode.left = leftRootnode.right = self.rootleftRoot.right = nodeself.root.left = nodeself.map[key] = nodeself.size += 1else:# 以下代码是淘汰策略,当不需要淘汰的时候if self.map.get(key):# 将该元素移动到最新使用的node = self.map.get(key)leftRoot = self.root.leftrightRoot = self.root.right# 更新元素中的值node.val = value# 移除使用的节点,将其移动到最后leftNode = node.leftrightNode = node.rightleftNode.right = rightNoderightNode.left = leftNode# 将该节点放到最后leftRoot = self.root.leftleftRoot.left = nodenode.left = leftRootnode.right = rightRootself.root.left = nodeself.root = rightNodeelse:deleteKey = self.root.keydel self.map[deleteKey]leftRoot = self.root.leftrightRoot = self.root.rightnode = Node()node.key = keynode.val = valuenode.left = leftRootnode.right = rightRootleftRoot.right = noderightRoot.left = nodeself.root = rightRootself.map[key] = nodeself.size += 1if __name__ == '__main__':cache = LRUCache(2)cache.put(1, 1)cache.put(2, 2)print(cache.get(1))cache.put(3, 3)print(cache.get(2))cache.put(4, 4)print(cache.get(1))print(cache.get(3))print(cache.get(4))
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。