leetcode专题训练146. LRU Cache

解法1：
解法1我是当作大模拟来做的。由于key如果被用，那么无论之前在什么位置，都要被换到最新使用的位置。所以一直在想什么数据结构可以灵活换位置，后来发现可以用链表，所以维护了一个链表，链表中的顺序由最远使用到最近使用。而且由于需要把最远使用的弹出，把最新使用的插入，所以链表的头和尾都需要有个指针指示。在本代码中，分别使用cache_head和cache_tail表示。而取键值的操作，为了不每次都从链表头遍历，我使用了一个dict数据结构，这个数据结构单纯的用于存储LRU中的键值，取值的复杂度为O(1)，由于要和链表中节点同步删除，所以还要在容量超过capacity时，删除字典中元素，复杂度为O(n)。
数据结构说完了，具体操作看代码中注释即可。

class Node:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.right = right

class LRUCache:

    def __init__(self, capacity: int):
    	# 若capacity非正数，那assert退出
        assert capacity > 0
        self.capacity = capacity
        self.cache_head = Node(0) # 链表头，空头
        self.cache_tail = self.cache_head # 链表尾
        self.now_len = 0 # 当前链表长度
        self.cache = {} # 存储key和value的dict

    def get(self, key: int) -> int:
        # 如果该值不存在于cache中，返回-1
        if key not in self.cache.keys():
            return -1
        else:
            # print("-----get-------")
            # 将p挪到链表最后，代表最近使用
            p = self.cache_head.right
            pre = self.cache_head
            while p is not None:
                if p.key == key:
                    # 已经是最常使用的了，不用再换位置了
                    if p.right is None:
                        break
                    pre.right = p.right
                    self.cache_tail.right = p
                    p.right = None
                    self.cache_tail = p
                    break
                p = p.right
                pre = pre.right

            # p = self.cache_head.right
            # while p is not None:
            #     print(p.key, " ", self.cache[p.key])
            #     p = p.right
            # print("-----end get-------")

            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        # print("-----put-------")
        if self.get(key) == -1:
            # 表已满，则删除最远使用节点
            if self.now_len == self.capacity:
                p = self.cache_head.right
                self.cache_head.right = p.right
                # print(p.right.key)
                # 删除字典中最不常用
                self.cache.pop(p.key)
                # 删除链表中节点
                del p
                self.now_len -= 1
            p = Node(key)
            self.cache_tail.right = p
            self.cache_tail = p
            self.now_len += 1

        # 顺序已经在self.get这个步骤中调整过了，所以此处只用赋值就行了
        self.cache[key] = value

        # p = self.cache_head.right
        # while p is not None:
        #     print(p.key, " ", self.cache[p.key])
        #     p = p.right
        # print("-----end put-------")

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

解法2：
看了题解，发现题解用了双向链表，同时dict中存储的是key和双向链表中节点的对应，而不是key和value的对应，且由于是双向链表，所以可以很好的将节点取出并搁到最后，非常巧妙。
在处理当前节点p的时候，由于是双向链表，p.left.right和p.right.left均要处理，一个都不能落下。

class Node:
    def __init__(self, key, value, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

class LRUCache:

    def __init__(self, capacity: int):
        assert capacity > 0
        self.capacity = capacity
        self.cache_head = Node(0, 0)
        self.cache_tail = self.cache_head
        self.now_len = 0
        self.cache = {}

    def get(self, key: int) -> int:
        # 如果该值不存在于cache中，返回-1
        if key not in self.cache.keys():
            return -1
        else:
            p = self.cache[key]

            # 已经是最常使用的了，不用再换位置了
            if p.right is None:
                return p.value

            # 将p挪到最后，代表最近使用
            p1 = p.left
            p.left.right = p.right
            p.right.left = p.left
            p.left = self.cache_tail
            p2 = p.right
            self.cache_tail.right = p
            p.right = None
            self.cache_tail = p

            return p.value

    def put(self, key: int, value: int) -> None:
        if self.get(key) == -1:
            # 表已满，则删除最远使用节点
            if self.now_len == self.capacity:
                p = self.cache_head.right
                self.cache_head.right = p.right
                if p.right is not None:
                    p.right.left = self.cache_head
                # 删除字典中最不常用
                self.cache.pop(p.key)
                # 删除链表中节点
                del p
                self.now_len -= 1
            p = Node(key, value, left=self.cache_tail)
            self.cache_tail.right = p
            self.cache_tail = p
            self.now_len += 1
            self.cache[key] = p
        else:
            # 顺序已经在self.get这个步骤中调整过了，所以此处只用赋值就行了
            self.cache_tail.value = value

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

最后

以上就是鳗鱼世界为你收集整理的leetcode专题训练146. LRU Cache的全部内容，希望文章能够帮你解决leetcode专题训练146. LRU Cache所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。