每日一题 146. LRU 缓存

难度：中等

由于周日没做，今天又是困难题，所以假装今天是周日

思路：

1. 在字典结构的基础之上完成三个要求
2. 显然题目要求构建一个有序字典（当然不使用OrderedDict），由于 key 是唯一的，因此可以将 value 设置为一个三元组，分别保存 value 本身、右 key、左 key
3. 当第一次插入元素，或者 capacity 为1或2时，会涉及到头即是尾或者左 key 为头等等需要讨论的情况。所以在初始字典中加入两个默认的三元组作为头和尾，这样所有的元素加入时和变更位置时都只需讨论一种情况
4. 总之可以理解为”向链表添加或删除元素“的问题

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dic = {-1:[-1,-1,-2], -2:[-2,-1,-2]}

    def get(self, key: int) -> int:
        t = self.dic.get(key)
        if t is None:
            return -1
        if t[2] != -2:  
            self.dic[t[2]][1] = t[1]
            self.dic[t[1]][2] = t[2]  
            self.dic[key][1] = self.dic[-2][1]
            self.dic[key][2] = -2
            self.dic[self.dic[-2][1]][2] = key
            self.dic[-2][1] = key
            
        return t[0]

    def put(self, key: int, value: int) -> None:
        t = self.dic.get(key)
        if t is None:
            if self.capacity > 0:
                self.capacity -= 1
            else:
                d = self.dic[-1][2]
                self.dic[-1][2] = self.dic[d][2]
                self.dic[self.dic[d][2]][1] = -1
                self.dic.pop(d)

            self.dic[key] = [value, self.dic[-2][1], -2]
            self.dic[self.dic[-2][1]][2] = key
            self.dic[-2][1] = key

            return

        self.dic[key][0] = value
        self.get(key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40