[Python] Map and Double Linked List


  • 0
    O

    They are in the progress of updating the graph distribution, so i can not see my codes' performance.

    # 设计一个数据结构,使得满足以下两种操作:
    # 1、get(key):如果key值存在得到key值对应的value,不存在返回-1
    # 2、set(key, value):设置或者插入一个新的key值
    
    # 思路:
    # 使用map结构,保存key值到一个node节点的映射
    # 这个node节点,是一个双向链表的节点。
    # 当通过key值访问的时候,先通过map结构O(1)时间复杂度定位到节点,再通过节点得到值,并且将该节点移动到双向链表的结尾
    # 当容量溢出的时候,就删除双向链表的头结点。
    
    # 双向链表节点的数据结构
    # 加入了key是为了,在删除节点的时候同时也要删除mapping结构里面的键值对,所以加入了key
    class DoubleLinkedListNode(object):
    
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.left = None
            self.right = None
    
    
    class LRUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.capacity = capacity  # 设置LRU cache的容量
            self.currSize = 0  # 当前LRU cache的大小
            self.mapping = {}
            self.head = DoubleLinkedListNode(0, 0)
            self.tail = self.head
    
        def changeNodeToTail(self, node):
            if self.tail == node:
                return
    
            # delete the node from double linked list
            preNode = node.left
            nextNode = node.right
            preNode.right = nextNode
            nextNode.left = preNode
    
            # append the node to the tail of the list
            self.tail.right = node
            node.left = self.tail
            node.right = None  # add the end flag.
            self.tail = node  # change the tail node
    
        def addNodeToTail(self, node):
            self.tail.right = node
            node.left = self.tail
            self.tail = node
            self.currSize += 1
    
        def deleteNode(self):
            if self.capacity < 1:
                return
    
            deletedKey = self.head.right.key
            if self.capacity == 1:  # 只有1,则直接置self.head = 0
                self.head.right = None
                self.tail = self.head
            else:
                tmp = self.head.right.right
                self.head.right = tmp
                tmp.left = self.head
            self.currSize -= 1
    
            return deletedKey
    
        def get(self, key):
            """
            :rtype: int
            """
            if key in self.mapping:
                currNode = self.mapping[key]
                self.changeNodeToTail(currNode)
                return currNode.val
    
            return -1
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: nothing
            """
            # 节点已经存在LRU里面,重置val即可
            if key in self.mapping:
                self.mapping[key].val = value
                self.changeNodeToTail(self.mapping[key])
                return
    
            # 不存在,则插入节点
            newNode = DoubleLinkedListNode(key, value)
            # 先检查size与capacity的大小关系
            # 相等,则先删除头部节点。
            if self.currSize == self.capacity:
                deleteKey = self.deleteNode()
                self.mapping.pop(deleteKey)
    
            # 向双向链表和map中加入item
            self.addNodeToTail(newNode)
            self.mapping[key] = newNode
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.