LeetCode 146 LRU缓存机制

代码(Python3):
题目描述:

实现LRU(最近最少使用)缓存机制,即一个数据结构.当缓存的容量达到上线时,删除最近最少使用的数据,用于存储新到来的数据.在O(1)的时间复杂度内实现get和put操作.

Screenshot 2019-08-26 15:48:36.png

解题思路:
哈希表+双向链表
双向链表用来最近使用的先后顺序存储数据. 最近访问的在后.
哈希表用来存储当前已有的数据,对应的链表节点的引用值, 这是为了实现O(1)时间复杂度.

class CacheNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None
    
class LRUCache:

    def __init__(self, capacity: int):
        self.nums = dict()
        self.head = CacheNode(-1, -1)
        self.tail = self.head
        self.length = 0
        self.capacity = capacity
    
# 用于调试
    def debug(self):
        # for key in self.nums.keys():
        #     print (key, self.nums[key].value)
        # cur = self.head
        # _list = ''
        # while(cur):
        #     _list += '{}:{}'.format(cur.key, cur.value)
        #     _list += '->'
        #     cur = cur.next
        # print (_list)
        # print ('tail:', self.tail.value)
        pass
    
    def get(self, key: int) -> int:
        print ('begin get')
        self.debug()
        
        if not key in self.nums.keys():
            # print ('not in', key)
            return -1
        if self.tail.key == key:
            return self.tail.value
        ref = self.nums[key]
        value = self.nums[key].value
        ref_prev = self.nums[key].prev
        ref_next = self.nums[key].next
        ref_prev.next = ref_next
        if ref_next:
            ref_next.prev = ref_prev
        self.tail.next = ref
        ref.prev = self.tail
        ref.next = None
        self.tail = ref
        
        print ('after get')
        self.debug()
        
        return value
        
    def put(self, key: int, value: int) -> None:
        if key not in self.nums.keys():
            if self.length == self.capacity:           
                if self.capacity != 1:
                    self.head.next.next.prev = self.head
                del self.nums[self.head.next.key]
                self.head.next = self.head.next.next
                self.length -= 1
                if self.head.next == None:
                    self.tail = self.head

                print ('after del')
                self.debug()
            # 创建新节点  
            newNode = CacheNode(key, value)
            newNode.prev = self.tail
            newNode.next = None
            self.tail.next = newNode
            self.tail = newNode
            self.nums[key] = newNode
            self.length += 1
        else:
            if self.tail.key == key:
                self.tail.value = value
            else:
                ref = self.nums[key]
                ref.value = value
                ref_prev = self.nums[key].prev
                ref_next = self.nums[key].next
                ref_prev.next = ref_next
                if ref_next:
                    ref_next.prev = ref_prev
                self.tail.next = ref
                ref.prev = self.tail
                ref.next = None
                self.tail = ref
        #调试
        print ('after put')
        self.debug()
        
        return 

在LeetCode的官方题解中有两处亮点:

1. 直接继承OrderdDict, 这个类具有get, put操作均为O(1)时间复杂度的特点.
2. 使用双线链表时,把head和tail均定义为虚节点,这样就省去了很多边界判断的情况.